题解 | #[HNOI2003]激光炸弹#

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=5010;

int s[N][N];
int cnt,r;
int n,m;

int main()
{
    cin>>cnt>>r;
    r=min(5001,r);
    int x,y,val;
    n=m=5001;
    for(int i=0; i<cnt; i++)
    {
        cin>>x>>y>>val;
        x++,y++;
        s[x][y]+=val;
    }
    n=max(n,x),m=max(m,y);
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
    
    int res=0;
    for(int i=r; i<=n; i++)
        for(int j=r; j<=m; j++)
        {
            res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
        }
    
    cout<<res;
    
    
    
    
    return 0;
}