二维前缀和

题目

#include<iostream>
using namespace std;
const   int N=5010;
int sum[N][N];//题目不允许我们开两个二维的    
int s,r;
int maxx,maxy,ans; int main()
{
   
    cin>>s>>r;
    r=min(r,5000);
    maxx=maxy=r;//保证maxx和maxy大于等于r while(s--)
    {
   
        int a,b,c;
        cin>>a>>b>>c;
        sum[a+1][b+1]+=c;
        maxx=max(maxx,a+1);
        maxy=max(maxy,b+1);
    }
    for(int i=1;i<=maxx;i++)
    for(int j=1;j<=maxy;j++)
    sum[i][j]+=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1];
    for(int i=r;i<=maxx;i++)
    for(int j=r;j<=maxy;j++)
    ans=max(ans,sum[i][j]-sum[i-r][j]-sum[i][j-r]+sum[i-r][j-r]);
    printf("%d\n",ans);
    return 0;
    
}