题目链接：

https://www.luogu.org/problemnew/show/P2280

思路：

简单的二维前缀和，最后扫描一遍求

max(ans,f[i][j]+f[i-r][j-r]-f[i-r][j]-f[i][j-r]);

两个操作时间复杂度都是N方

注意细节：

• mx,my初始值赋值为边长，否则会有一个点WA
• x,y因为从0开始，都加1方便处理
• 第二遍扫描时，从r开始扫描
• 因为v值较小，可以用short，不过我很好奇为什么不能用char

#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=5005;
int n,r;
short int map[5005][5005];
int f[5005][5005],mx=0,my=0;
template void read(T & x)
{
int ne=0;char c;
while(!isdigit(c=getchar()))ne=c=='-';
x=c-48;
while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
x=ne?-x:x;
return;
}
int main()
{
int x,y,v,ans=0;
read(n),read(r);mx=r,my=r;
for(register int i=1;i<=n;i++)
{
read(x),read(y),read(v);
x++,y++;
map[x][y]=v;
mx=max(mx,x),my=max(my,y);
}
for(register int i=1;i<=mx;i++)
for(register int j=1;j<=my;j++)
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+map[i][j];
for(register int i=r;i<=mx;i++)
for(register int j=r;j<=my;j++)
ans=max(ans,f[i][j]+f[i-r][j-r]-f[i-r][j]-f[i][j-r]);
printf("%d\n",ans);
return 0;
}