-
题目链接：
-
思路：
简单的二维前缀和，最后扫描一遍求
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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=5005;
int n,r;
short int map[5005][5005];
int f[5005][5005],mx=0,my=0;
template <class T>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
",ans);
return 0;
}