题目链接: https://vjudge.net/contest/537370#problem/E

题意

一种新型的激光炸弹，可以摧毁一个边长为 m 的正方形内的所有目标。现在地图上有 n 个目标，用整数 xi​ , yi​ 表示目标在地图上的位置，每个目标都有一个价值 vi​ .激光炸弹的投放是通过卫星定位的，但其有一个缺点，就是其爆破范围，即那个边长为 m 的边必须与 x 轴, y 轴平行。若目标位于爆破正方形的边上，该目标不会被摧毁。

现在你的任务是计算一颗炸弹最多能炸掉地图上总价值为多少的目标。

1≤n≤1e4，0≤xi,yi≤5×1e3，1≤m≤5×1e3，1≤vi<100

思路

前缀和扫描每一个正方形块的价值，求最大值即可。

复杂度 O(n^2)。

代码

#include <cstdio>
#include <algorithm>

#define NL putchar(10);

const int maxN = 5e3+5;

int num[maxN][maxN];

int main() {
  int n, m; scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    int x, y, v; scanf("%d%d%d", &x, &y, &v);
    num[x+1][y+1] = v;
  }

  for(int x = 1; x < maxN; ++x) {
    for(int y = 1; y < maxN; ++y) {
      num[x][y] += num[x][y-1];
    }
  }

  for(int x = 1; x < maxN; ++x) {
    for(int y = 1; y < maxN; ++y) {
      num[x][y] += num[x-1][y];
    }
  }

  int max = -1;
  for(int x = maxN-1; x >= m; --x) {
    for(int y = maxN-1; y >= m; --y) {
      int cur = num[x][y] + num[x-m][y-m] - num[x][y-m] - num[x-m][y];
      max = std::max(max, cur);
    }
  }

  printf("%d", max);

  return 0;
}