AcWing 99. 激光炸弹(Python)
原题链接
简单
作者:
习学学
,
2021-01-26 00:22:33
,
所有人可见
,
阅读 371
N, R = map(int, input().split())
grids = [[0] * 5010 for _ in range(5010)]
n, m = R, R
for _ in range(N):
i, j, w = map(int, input().split())
n, m = max(n, i+1), max(m, j+1)
grids[i+1][j+1] += w
for i in range(1, n+1):
for j in range(1, m+1):
grids[i][j] += grids[i-1][j] + grids[i][j-1] - grids[i-1][j-1]
res = 0
for i in range(1, n+1):
for j in range(1, m+1):
rx, ry = min(n, i+R-1), min(m, j+R-1)
cnt = grids[rx][ry] + grids[i-1][j-1] - grids[i-1][ry] - grids[rx][j-1]
res = max(res, cnt)
print(res)