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

#include <iostream>
#include<algorithm>
using namespace std;
int arr[5005][5005];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int x,y;
    int n,r;cin>>n>>r;
    int a=r,b=r;//将初始边界设为r，防止点在0行0列的情况
    for(int i=0;i<n;i++)
    {
        int x,y,v;
        cin>>x>>y>>v;arr[x+1][y+1]=v;//将坐标进行平移，防止越界
        a=max(a,x+1);
        b=max(b,y+1);
    }
    
    for(int i=1;i<=a;i++)
    {
        for(int j=1;j<=b;j++)//所有点在1到a+1,1到b+1上；
        {
           arr[i][j]+=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];   //利用二维前缀进行处理；
        }
    }
    int ans=0;
    {
        for(int j=r;j<=b;j++)
        {
        ans=max(ans,arr[i][j]-arr[i-r][j]-arr[i][j-r]+arr[i-r][j-r]);
        }
    }
    cout<<ans;
    return 0;
}