2024-2-28-99-激光炸弹.cpp

发表于 更新于 阅读次数： 本文字数： 655 阅读时长 ≈ 1 分钟

2024-2-28-99-激光炸弹.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5010;

int n,m; int cnt,r; int s[N][N];

int main() { cin>>cnt>>r; r=min(5001,r); n=m=r;

while(cnt--)
{
    int x,y,w;
    cin>>x>>y>>w;
    x++,y++;
    n=max(n,x),m=max(m,y);
    s[x][y]+=w;
}

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
        s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];//二维前缀和

int res=0;
for(int i=r;i<=n;i++)
    for(int j=r;j<=m;j++)
        res=max(res,s[i][j]-s[i-r][j]-s[i][j-r]+s[i-r][j-r]); //计算滑动窗口中的最大值

cout<<res<<endl;
return 0;
}