题目描述

N, R = map(int, input().split())
R = min(R, 5001)

a = [[0 for _ in range(5003)] for _ in range(5003)]
s = [[0 for _ in range(5005)] for _ in range(5005)]

for _ in range(N):
xi, yi, wi = map(int, input().split())
a[xi + 1][yi + 1] += wi

计算二维前缀和

for i in range(1, len(a)):
for j in range(1, len(a[0])):
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j]

print(s[1][1])=1

print(s[2][2])=2求解没问题

定义矩阵和计算函数，确保索引不越界

def sum_matrix(x1, y1, x2, y2):
return s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]

print(sum_matrix(0,0,2,2))不包括左下角那个点，按道理需要包括

获取最大区域和

max_sum = 0
for i in range(1, 5003 - R + 1):
for j in range(1, 5003 - R + 1):
current_sum = sum_matrix(i, j, i + R - 1, j + R - 1)
max_sum = max(max_sum, current_sum)

print(max_sum)

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla