专栏首页奇妙的算法世界激光炸弹(二维前缀和)

激光炸弹(二维前缀和)

题意描述

思路

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N][N];
int main(){
    int n,r,m,u;scanf("%d%d",&n,&r);
    u=n;
    r=min(r,5001);
    n=m=r;
    for(int i=0;i<u;i++){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        a[x+1][y+1]+=z;
        n=max(n,x+1);
        m=max(m,y+1);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
        }
    }
    int ans=0;
    for(int i=r;i<=n;i++){
        for(int j=r;j<=m;j++){
            ans=max(ans,a[i][j]-a[i-r][j]-a[i][j-r]+a[i-r][j-r]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2019河南科技学院发现杯

    来到学校后第一次参加算法比赛,听学长说去年的难度非常高,所以这次比赛目标就是得到分数。但今年的难度整体偏低,第八题做的比较懵,第十题不会做(连题都看不懂 ),其...

    dejavu1zz
  • 最高的牛(差分)

    有 N 头牛站成一行,被编队为1、2、3…N,每头牛的身高都为整数。 当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。 现在,我们只知道其中最高...

    dejavu1zz
  • HDOJ-1711(kmp算法)

    Given two sequences of numbers : a[1], a[2], … , a[N], and b[1], b[2], … , b[M] ...

    dejavu1zz
  • 【2020HBU天梯赛训练】7-51 分而治之

    分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。...

    韩旭051
  • 【LeetCode第 160 场周赛】5239. 循环码排列

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 西南民族大学程序竞赛

    No matter what activities you join,whether you want or not, you could gain unexp...

    AngelNH
  • 洛谷P1941 飞扬的小鸟(背包 dp)

    很显然的dp,设\(f[i][j]\)表示第\(i\)个位置,高度为\(j\)的最小步数

    attack
  • 通吃岛屿问题

    在秋招及实习期间发现岛屿问题在面试中会被经常问到,本节来把leetcode上的所有岛屿问题通吃一遍。

    公众号guangcity
  • 挑战程序竞赛系列(95):3.6数值积分(1)

    挑战程序竞赛系列(95):3.6数值积分(1) 传送门:AOJ 1313: Intersection of Two Prisms 题意: 有一个侧棱与Z轴平行...

    用户1147447
  • 2019河南科技学院发现杯

    来到学校后第一次参加算法比赛,听学长说去年的难度非常高,所以这次比赛目标就是得到分数。但今年的难度整体偏低,第八题做的比较懵,第十题不会做(连题都看不懂 ),其...

    dejavu1zz

扫码关注云+社区

领取腾讯云代金券