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

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>> v(5010,vector<int> (5010));
int get(int x1,int y1,int x2,int y2){
    if(x2>5000&&y2>5000) {
        x2=5000;
        y2=5000;
    }//处理边界
    else if(x2>5000&&y2<=5000) x2=5000;//处理边界
    else if(x2<5000&&y2>5000)  y2=5000;//处理边界
    if(x1==0&&y1==0) return v[x2][y2];
    if(x1==0&&y1!=0) return v[x2][y2]-v[x2][y1-1];
    if(y1==0&&x1!=0) return v[x2][y2]-v[x1-1][y2];
    if(x1!=0&&y1!=0) return v[x2][y2]-v[x2][y1-1]-v[x1-1][y2]+v[x1-1][y1-1];
    return 0;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    int R;
    cin>>R;
    int value;
    int x,y;
    for(int i=0;i<n;i++){
         cin>>x>>y;
         cin>>value;
        v[x][y]=value;
    }
    int max=0;

    for(int i=0;i<=5000;i++){
        for(int j=0;j<=5000;j++){
            if(i==0&&j!=0) v[0][j]=v[0][j]+v[0][j-1];
            if(j==0&&i!=0) v[i][0]=v[i][0]+v[i-1][0];
            if(j!=0&&i!=0) v[i][j]=v[i][j]+v[i][j-1]+v[i-1][j]-v[i-1][j-1];
        }
    }
   for(int i=0;i<=5000;i++){
     for(int j=0;j<=5000;j++){
         int M=get(i,j,i+R-1,j+R-1);//（i，j）表示爆炸范围的正方形左上角，（i+R-1，j+R-1）是右上角       
         if(M>max){
             max=M;
         }
     }
   
   }
   cout<<max;
    return 0;
}