정수 N개의 합 3

걍 디피랑 다를바가 없다.
누적합이라곤 하는데...
무튼!

근데 이건 2차원이니까, 어떻게 처리할까?
각 열 별로 합을 구해놓고 처리를 할까? 했지만
풀이로는 각 y,x까지의 합을 저장해두고
필요한 값의 위치를 점화식으로 구하면 된다

n, k = map(int, input().split())
arr = [[0 for _ in range(n+1)]]+[[0]+list(map(int, input().split())) for _ in range(n)]

dp=[[0 for _ in range(n+1)]for _ in range(n+1)]

for y in range(1,n+1):
    for x in range(1,n+1):
        dp[y][x]=dp[y-1][x]+dp[y][x-1]+arr[y][x]-dp[y-1][x-1]

value=0
for y in range(k,n+1):
    for x in range(k,n+1):
        value=max(value,(dp[y][x]+dp[y-k][x-k]-dp[y-k][x]-dp[y][x-k]))

print(value)