a026. APIO2009 1.采油区域
===
先了解用前綴和 算中間任意k*k塊的總和
https://blog.csdn.net/weixin_44176696/article/details/104988020
算出三塊不同位置的組合有6種
寫了兩個多小時 29行的迴圈圖片前面4種方案看不董代碼!
[image](https://hackmd.io/_uploads/BkazY5khp.png)

def kksum(x1, y1, x2, y2, z):
    return z[x2][y2] - z[x1 - 1][y2] - z[x2][y1 - 1] + z[x1 - 1][y1 - 1]
m, n, k = map(int, input().split())
a = [[0] * (n + 1) for _ in range(m + 1)]
ul = [[0] * (n + 1) for _ in range(m + 1)]
ur = [[0] * (n + 1) for _ in range(m + 1)]
dl = [[0] * (n + 1) for _ in range(m + 1)]
dr = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):#行的前綴和
    row = list(map(int, input().split()))
    for j in range(1, n + 1):#列的前綴和
        a[i][j] = row[j - 1] + a[i][j - 1]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        a[i][j] += a[i - 1][j]
for i in range(k, m + 1):#ul
    for j in range(k, n + 1):
        ul[i][j] = max(kksum(i - k + 1, j - k + 1, i, j, a), ul[i - 1][j], ul[i][j - 1])
for i in range(k, m + 1):#ur
    for j in range(n - k + 1, 0, -1):
        ur[i][j] = max(kksum(i - k + 1, j, i, j + k - 1, a), ur[i - 1][j], ur[i][j + 1])
for i in range(m - k + 1, 0, -1):#dl
    for j in range(k, n + 1):
        dl[i][j] = max(kksum(i, j - k + 1, i + k - 1, j, a), dl[i + 1][j], dl[i][j - 1])
for i in range(m - k + 1, 0, -1):#dr
    for j in range(n - k + 1, 0, -1):
        dr[i][j] = max(kksum(i, j, i + k - 1, j + k - 1, a), dr[i + 1][j], dr[i][j + 1])
ans = 0

for i in range(k, m - k):
    up = ul[i][n]#上面那塊
    dw = dl[i + k][n]#下面那塊
    mid = 0
    for j in range(k, n + 1):
        mid = max(mid, kksum(i + 1, j - k + 1, i + k, j, a)) #中間最大那塊
    ans = max(ans, up + dw + mid)
for j in range(k, n - k):
    le = max(ul[k][j], dl[k + 1][j])#左邊最大塊
    ri = max(ur[k][j + k], dr[k + 1][j + k])#右邊最大塊
    mid = 0
    for i in range(k, m + 1):
        mid = max(mid, kksum(i - k + 1, j + 1, i, j + k, a)) #中間最大那塊
    ans = max(ans, le + ri + mid)
print(ans)