题目
我的思路
用二维前缀和计算,先对有价值的赋给数组,也求出最大的x,y的下标值,然后构造二维前缀和,再枚举每次的起始点计算最大价值
代码
```c++
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=5010;
int w[N][N];
LL s[N][N];
int main()
{
int n,r;
cin>>n>>r;
int maxx=0,maxy=0;
while(n--)
{
int x,y,val;
cin>>x>>y>>val;
w[x+1][y+1]=val;
maxx=max(maxx,x+1);
maxy=max(maxy,y+1);
}
for(int i=1;i<=maxx;i++)
for(int j=1;j<=maxy;j++)
s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+w[i][j];
LL sum=0;
for(int i=1;i<=maxx;i++)
for(int j=1;j<=maxy;j++)
sum=max(sum,s[i+r-1][j+r-1]-s[i+r-1][j-1]-s[i-1][j+r-1]-s[i-1][j-1]);
cout<<sum<<endl;
return 0;
}
```