38 lines
1.3 KiB
C++
38 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
|
||
const int N = 5010, M = 5001;
|
||
// 前缀和数组
|
||
int s[N][N];
|
||
|
||
int main() {
|
||
// n:点的数量，r:边长
|
||
int n, r;
|
||
cin >> n >> r;
|
||
|
||
// 这里本题数据有些坑，r有时输入会比我们整个矩阵大，所以这里设置输入的r过大，就直接取M
|
||
r = min(r, M); // r太大，对于我们来说没有意义，因为它>5001时，就把所有位置全部摧毁掉~
|
||
|
||
for (int i = 1; i <= n; i++) {
|
||
int x, y, w;
|
||
cin >> x >> y >> w;
|
||
// 因为每题的(x,y)是默认下标从0开始，与前缀和的习惯不太相符，所以，这里直接将原坐标x+1,y+1，映射到下标从(1,1)开始
|
||
x++, y++; // 0≤Xi,Yi≤5000
|
||
s[x][y] += w; // 不同目标可能在同一位置,s数组同时也充当了a数组
|
||
}
|
||
|
||
// 二维前缀和公式
|
||
for (int i = 1; i <= M; i++)
|
||
for (int j = 1; j <= M; j++)
|
||
s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
|
||
|
||
// 枚举所有边长为r的正方形(枚举右下角)，取最大值就OK了
|
||
int res = 0;
|
||
for (int i = r; i <= M; i++)
|
||
for (int j = r; j <= M; j++) // 二维前缀和应用
|
||
res = max(res, s[i][j] - s[i - r][j] - s[i][j - r] + s[i - r][j - r]);
|
||
|
||
// 输出结果
|
||
cout << res << endl;
|
||
return 0;
|
||
} |