本来是怕爆int写了long long
结果爆memory了
改int还是爆
就把前缀和矩阵和值矩阵合并了
#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
int n, r;
typedef int ll;
// 担心爆int
ll x, y, v;
ll value[N][N];
int main()
{
cin >> n >> r;
for(int i = 1; i <= n; i ++)
{
cin >> x >> y >> v;
value[++x][++y] += v;
}
// for(int i = 1; i <= 5; i ++)
// {
// for (int j = 1; j <= 5; j ++)
// cout << value[i][j] << ' ';
// cout << endl;
// }
for(int i = 1; i <= 5000; i ++)
for(int j = 1; j <= 5000; j ++)
value[i][j] += value[i-1][j] + value[i][j-1] - value[i-1][j-1];
// 可以在读入的同时求横纵坐标范围,但我觉得没必要
// 毕竟算法的尿性就是给你最坏情况
// for(int i = 1; i <= 5; i ++)
// {
// for (int j = 1; j <= 5; j ++)
// cout << value[i][j] << ' ';
// cout << endl;
// }
int res = 0;
for(int i = 0; i < 5000 - r + 1; i ++)
for(int j = 0; j < 5000 - r + 1; j ++)
res = max(res, value[i][j]+value[i+r][j+r]-value[i][j+r]-value[i+r][j]);
cout << res << endl;
return 0;
}