PythonでJOI難易度5を埋める #5
考えたこと
ひとつずつコストの和を取っていると間に合わないので、うまく計算量を減らす必要があります。そこで、累積和を使います。私も初めて使いましたが、二次元累積和というものらしい。
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)