acwing99. 激光炸弹

题目

题解

利用二维矩阵前缀和来计算每个半径为r的范围。

#include<iostream>
using namespace std;
const int N=5010;
int n,cnt,m,r,s[N][N];

int main(){
    cin>>cnt>>r;
    r=min(r,5001);
    n=m=r;
    while(cnt--){
        int x,y,w;
        scanf("%d%d%d",&x,&y,&w);
        x++,y++;
        n=max(n,x),m=max(y,m);
        s[x][y]+=w;
    }
    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 ans=0;
    for(int i=r;i<=n;i++){
        for(int j=r;j<=m;j++){
            ans=max(ans,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]);
        }
    }
    cout<<ans<<endl;
    return 0;
}