مربع

Main.py

n, m, k = list(map(int, input().split(" ")))

ps = [[0] * (m + 1) for i in range(n + 1)]

A = []
for i in range(n):
    B = list(map(int, input().split(" ")))
    for j in range(m):
        ps[i + 1][j + 1] = B[j] + ps[i][j + 1] + ps[i + 1][j] - ps[i][j]

curr = n * m - ps[n][m]
ans = 0

def getNumberOfZeroes_1(x, y) :
    return ps[x + k][y + k] - ps[x][y + k] - ps[x + k][y] + ps[x][y]

def getNumberOfZeroes_2(x1, y1, x2, y2) :
    return ps[x2][y2] - ps[x1][y2] - ps[x2][y1] + ps[x1][y1]


for x1 in range(n - k + 1):
    for y1 in range(m - k + 1):
        for x2 in range(n - k + 1):
            for y2 in range(m - k + 1):
                z1 = getNumberOfZeroes_1(x1, y1)
                z2 = getNumberOfZeroes_1(x2, y2)
                mnRow = max(x1, x2)
                mxRow = min(x1, x2) + k
                mnCol = max(y1, y2)
                mxCol = min(y1, y2) + k
                if(mnRow >= mxRow or mnCol >= mxCol) :
                    ans = max(ans, z1 + z2)
                else:
                    ans = max(ans, z1 + z2 - getNumberOfZeroes_2(mnRow, mnCol, mxRow, mxCol))

print(ans + curr)