[Python] ABC005 D

問題

D – おいしいたこ焼きの焼き方

解説を読んでも解けなかった…。

回答

参考

累積和を何も考えずに書けるようにする！

回答はpythonであるということ以外は上の写経です。

import sys
# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    D = [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    P = [int(input()) for _ in range(Q)]

    # S[i][j](0,0)〜(i,j)までのたこ焼きの美味しさの和
    S = [[0] * (N+1) for _ in range(N+1)]

    # たこ焼きの美味しさの累積和
    for i in range(N):
        for j in range(N):
            S[i+1][j+1] =  S[i][j+1] + S[i+1][j] - S[i][j] + D[i][j]
    
    #  value[s]面積sの長方形領域の総和の最大値
    value = [0] * (N**2 + 1)
    for x1 in range(N):
        for x2 in range(x1 + 1, N+1):
            for y1 in range(N):
                for y2 in range(y1+1, N+1):
                    area = (x2 - x1) * (y2 - y1)
                    sum = S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1]
                    value[area] = max(value[area], sum)
    
    
    # dp_2[s]面積s以下の長方形領域の総和の最大値
    for i in range((N)**2):
        value[i+1] = max(value[i+1], value[i])

    for p in P:
        print(value[p])


main()