当前位置：网站首页>HNOI2003-激光炸弹

HNOI2003-激光炸弹

2022-07-22 11:07:00 【ai_moe】

文章目录

题目详情
解题代码

题目详情

在这里插入图片描述

解题代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N =5010;

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

int main()
{
    
    scanf("%d %d",&cnt,&r);

    r=min(r,5001);
    
    m=n=r;
    
    while(cnt --)
    {
    
        int x,y,w;
        scanf("%d%d%d",&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][j]-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]);
            
    printf("%d",res);
    return 0;
}