激光炸弹题解

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

注意行列关系，着重区分哪个是行哪个是列，裸的二维前缀和

AC代码：

#include 
using namespace std;
int a[10010][10010];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,r,h,l;
    
    cin >> n >> r;
    l = r,h = r;
    for(int i = 0;i < n;i++){
        int x,y,z;
        cin >> x >> y >> z;
        x++,y++;
        h = max(h,x);
        l = max(l,y);
        a[x][y] += z;
    }
//     h++,l++;
    for(int i = 1;i <= h;i++){
        for(int j = 1;j <= l;j++){
            a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
        }
    }
    int ans = 0;
    for(int i = r;i <= h;i++){
        for(int j = r;j <= l;j++){
            ans = max(ans,a[i][j] - a[i - r][j] - a[i][j - r] + a[i - r][j - r]);
        }
    }
    cout << ans << endl;
    return 0;
}