[BOJ 11660]区間と5(Python)を求めます

質問する

区間と5を求めます

問題の説明

N<=1024,M<=10000の制限条件なので、フルナビゲーションを使用すると
M*N^2の時間の複雑さは、当然タイムアウトします.
したがって,DPを用いて解く必要があり,DPは2次元リストを用いる.
DP[i][j]は、(0,0)からiとjの和を求めることで値を入力する.

下図に示すように、緑色の部分を取得する必要がある場合は、DP表から黄色の部分を2つ削除し、赤色の部分は共通の部分なので、もう一度行う必要があります.

プールコード

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
graph = []
dp = [[0] * (n + 1) for _ in range(n + 1)]

for _ in range(n):
    graph.append(list(map(int, input().rstrip().split())))


# dp 채우기
for i in range(1, n + 1):
    for j in range(1, n + 1):
        dp[i][j] = graph[i - 1][j - 1] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

for _ in range(m):
    x1, y1, x2, y2 = map(int, input().split())
    print(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1])