输入样例:
2 1
0 0 1
1 1 1
输出样例:
1
解析:
二维前缀和,枚举每个正方形区间的最大值即可
本题只能开一个5000的二维数组,两个会MLE
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=5010,m=5005;
int n,r,sum[N][N];
int main(){
scanf("%d%d",&n,&r);
int maxx=0,maxy=0;
for(int i=1;i<=n;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
x++,y++;
sum[x][y]+=w;
maxx=max(maxx,x);
maxy=max(maxy,y);
}
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
if(r>=maxx&&r>=maxy){
cout<<sum[m][m];
return 0;
}
int res=0;
for(int i=1;i + r - 1 <=m;i++){
for(int j=1;j + r - 1 <= m;j++){
res=max(res,sum[i+r-1][j+r-1]-sum[i-1][j+r-1]-sum[i+r-1][j-1]+sum[i-1][j-1]);
}
}
cout<<res;
return 0;
}