思路：二维前缀和存价值。r>>x,y，所以先将r缩小，即 r=min(5001,r)。将xm和ym赋值为r，放置最后计算时越界。最后两重for循环，x和y从r开始遍历，然后差分。
#include <bits/stdc++.h> using namespace std; typedef long long int ll; const int maxn = 5055; int n, r; int b[maxn][maxn]; int main() { cin >> n >> r; r=min(5001,r); int xm = r, ym = r; for (int i = 1; i <= n; i++) { int x, y, w; cin >> x >> y >> w; x++, y++; xm = max(x, xm); ym = max(y, ym); b[x][y] += w; } for (int i = 1; i <= xm; i++) { for (int j = 1; j <= ym; j++) { b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1]; } } int res = 0; for (int i = r; i <= xm; i++) { for (int j = r; j <= ym; j++) { res = max(res, b[i][j] - b[i - r][j] - b[i][j - r] + b[i - r][j - r]); } } cout << res; }
