AcWing 99. 激光炸弹
原题链接
简单
作者:
喜欢日奈大可爱
,
2024-03-25 20:37:40
,
所有人可见
,
阅读 1
python3 二维前缀和
N, R = map(int, input().split(" "))
R = min (R, 5001)
s = [[0 for i in range(5010)]for j in range(5010)]
n = R
m = R
for i in range(N):
X, Y, W = map(int, input().split(" "))
n = max(n, X+1)
m = max(m, Y+1)
s[X+1][Y+1] += W
# 处理前缀和
for i in range(1, n+1):
for j in range(1, m+1):
s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]
res = 0
for i in range(R, n+1):
for j in range(R, m+1):
res = max(res, s[i][j] - s[i][j-R] - s[i-R][j] + s[i-R][j-R])
print(res)