激光炸弹
2023-03-07 09:16:01 时间
思想:
- 二维前缀和。
- 注意空间,数组不要开
long long
。 - 注意给出的坐标的下标是从 0 开始的。
- 循环遍历前缀和数组,维护一个最大价值即可。
代码:
#include <bits/stdc++.h>
using namespace std;
const int N = 5100;
int v[N][N];
int l, r;
void solve(){
int n, k; cin >> n >> k;
k = min(k, 5001);
l = r = k; //初始边界
for(int i = 1; i <= n; i ++){
int a, b, c; cin >> a >> b >> c;
v[a + 1][b + 1] += c;
l = max(a + 1, l), r = max(b + 1, r); //更新边界
}
for(int i = 1; i <= l; i ++){
for(int j = 1; j <= r; j ++){
v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1]; //二维前缀和
}
}
int res = 0;
for(int i = k; i <= l; i ++){
for(int j = k; j <= r; j ++){
res = max(res, v[i][j] - v[i - k][j] - v[i][j - k] + v[i - k][j - k]);
}
}
cout << res << endl;
}
int main(){
solve();
return 0;
}
相关文章
- 万字长文,带你搞懂 Kubernetes 网络模型
- 如何默认启动到 Linux 系统的旧内核
- Linux 中 九 个鲜为人知的 Neofetch 使用方法
- 浅谈软件开发的性能提升
- 六张图带你搞懂 Kubernetes 集群中几种常见的流量暴露方案
- 工程设计论——如何写好工程代码
- Tor 浏览器迎重大更新,可自动绕过互联网审查
- 如何监测微型的网站服务
- httpx:一个 Python Web 客户端
- 分布式系统中数据存储方案实践
- 你能说说Spring框架中Bean的生命周期吗?
- 使用 Netlify Forms 将联系表单添加到 React 应用程序
- 为什么说 TypeScript 的火爆是必然?
- 如何在 Linux 上设置 TFTP 服务器
- 轻量级动态线程池才是“王道”?
- Linux终端下的有趣的Ascii艺术文字生成工具
- 在 VirtualBox 安装 Arch Linux 的新手操作指南
- 用 ranger 在 Linux 终端管理你的文件
- 一文带你了解什么是 LRU 算法?
- 一分钟了解单点登录