A08 前缀和 二维前缀和

#include<bits/stdc++.h>
using namespace std;
int sum[5050][5050];
int main() 
{
    int n, r;scanf("%d%d", &n, &r);
    int mx=r, my=r;
    memset(sum, 0, sizeof(sum));
    for(int i=1, x, y, c; i<=n; i++) 
    {
        scanf("%d%d%d", &x, &y, &c);
        x++, y++;
        sum[x][y] += c;
        mx = max(mx, x), my = max(my, y);
    }
    for(int i=1; i<=mx; i++) 
        for(int j=1; j<=my; j++)
            sum[i][j] += sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];

    int ans=0;
    for(int i=r; i<=mx; i++)
        for(int j=r; j<=my; j++)
            ans = max(ans, sum[i][j] - sum[i-r][j] - sum[i][j-r] + sum[i-r][j-r]);
    printf("%d", ans);
    return 0;
}