一种新型的激光炸弹,可以摧毁一个边长为R的正方形内的所有的目标。 现在地图上有n(N ≤ 10000)个目标,用整数Xi,Yi(其值在[0,5000])表示目标在地图上的位置,每个目标都有一个价值。 激光炸弹的投放是通过卫星定位的,但其有一个缺点,就是其爆破范围,即那个边长为R的正方形的边必须和x,y轴平行。 若目标位于爆破正方形的边上,该目标将不会被摧毁。

输入格式

输入文件的第一行为正整数n和正整数R,接下来的n行每行有3个正整数,分别表示 xi,yi ,vi 。

输出格式

输出文件仅有一个正整数,表示一颗炸弹最多能炸掉地图上总价值为多少的目标(结果不会超过32767)。

数据范围 对于10

输入样例:

2 1
0 0 1
1 1 1

输出样例:

1

题目分析

二维前缀和 二维差分

代码实现

#include <iostream>
using namespace std;
const int N = 5e3 + 10;

int n, r, x, y, v, ans;
int g[N][N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> r;
    while(n--) {
        cin >> x >> y >> v;
        g[x + 1][y + 1] += v;
    }
    for(int i = 1; i < N; ++i) 
        for(int j = 1; j < N; ++j) 
            g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
    for(int i = r; i < N; ++i)
        for(int j = r; j < N; ++j)
            ans = max(ans, g[i][j] - g[i - r][j] - g[i][j - r] + g[i - r][j - r]);
    cout << ans;
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status