AcWing-99. 激光炸弹 【 二维前缀和 】 题解

目录

• ​​1.题目​​
• ​​2.代码​​

1.题目

2.代码

#include<iostream>
#include<cstdio>
#include<algorithm>
const int maxn = 5e3 + 10;
using namespace std;
int f[maxn][maxn];
int main()
{
  int N, R,n,m;
  cin >> N >> R;
  n = R, m = R;
  for (int i = 1; i <= N; i++)
  {
    int x, y, w;
    cin >> x >> y >> w;
    x++,y++;
    n = max(n, x);
    m = max(m, y);
    f[x][y] += w;
  }
  int ans = 0;
  for (int i = 1; i <= n; i++)
  {
    for (int j = 1; j <= m; j++)
    {
      f[i][j] += f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1];
    }
  }
  for (int i = R; i <= n; i++)
  {
    for (int j = R; j <= m; j++)
    {
      ans = max(ans, f[i][j] - f[i][j - R] - f[i - R][j] + f[i - R][j - R]);
    }
  }
  cout << ans << endl;
  return 0;
}