PythonでJOI難易度5を埋める #5

mall - ショッピングモール (Mall)

考えたこと
ひとつずつコストの和を取っていると間に合わないので、うまく計算量を減らす必要があります。そこで、累積和を使います。私も初めて使いましたが、二次元累積和というものらしい。

m, n = map(int,input().split())
a, b = map(int,input().split())
xy = [list(map(int,input().split())) for _ in range(n)]


for i in range(n):
    for j in range(m):
        if xy[i][j] == -1:
            xy[i][j] = 10 ** 8


for i in range(n):
    for j in range(m):
        if i == 0 and j != 0:
            xy[i][j] += xy[0][j - 1]

        elif i != 0 and j == 0:
            xy[i][j] += xy[i - 1][j]

        elif i != 0 and j != 0:
            xy[i][j] += xy[i - 1][j] + xy[i][j - 1] - xy[i - 1][j - 1]

#import pprint
#pprint.pprint(xy)

ans = float('inf')

for i in range(b-1, n):
    for j in range(a-1, m):
        cost = 0
        cost += xy[i][j]

        h, w = i - b, j - a

        if h >= 0:
            cost -= xy[h][j]
        if w >= 0:
            cost -= xy[i][w]
        if h >= 0 and w >= 0:
            cost += xy[h][w]

        ans = min(ans,cost)

print(ans)

参考にした記事
累積和