Description

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

Input

输入文件的第一行为正整数 \(n\) 和正整数 \(R\), 接下来的 \(n\) 行每行有 \(3\) 个正整数, 分别表示 \(X_i, Y_i, P_i\), 其中 \(P_i\) 代表该炸弹的权值.

Output

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

Sample Input

2 1
0 0 1
1 1 1

Sample Output

1

Explanation

不看题目都知道是矩形前缀和...... 但是第一次交上去还没有 Judge 就 TLE 了是什么情况...... 后来一查看发现数组开得略大 (而且常数不是一般的大, 还开了 long long)

仔细看了一眼发现其实用 short 就可以了, 开开心心交上去发现虽然没有 CE 但是实际上 TLE 直接滚粗了......

看了网上另一个代码, 发现他的常数不知道比我低到哪里去, 只用了不到 20 个指令就把问题解决了 (看来我的常数能力还需要加强)

结果交上去花了 8s 时间. 话说前面那些几十毫秒的人都是怎么过的 TAT

顺便附上 TLE 代码 (虽然能够工作)


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define maximize(__x,__y) __x=max(__x,__y)
using namespace std;
typedef long long lli;
const int maxn = 5100;

int n, R;
short arr[maxn][maxn],
    pref_hor[maxn][maxn],
    pref_ver[maxn][maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &R);
    for (int i = 1, a, b, c; i <= n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        arr[a+1][b+1] += c;
    }
    // Setting properties.
    int m = 5001;
    for (int i = 1; i <= m; i++) {
        pref_hor[i][0] = 0;
        for (int j = 1; j <= R-1; j++)
            pref_hor[i][0] += arr[i][j];
        for (int j = 1; j + R-1 <= m; j++)
            pref_hor[i][j] = pref_hor[i][j - 1]
                - arr[i][j-1] + arr[i][j+R-1];
        pref_hor[i][0] = 0;
    }
    for (int j = 1; j + R-1 <= m; j++) {
        pref_ver[0][j] = 0;
        for (int i = 1; i <= R-1; i++)
            pref_ver[0][j] += pref_hor[i][j];
        for (int i = 1; i + R-1 <= m; i++)
            pref_ver[i][j] = pref_ver[i - 1][j]
                - pref_hor[i-1][j] + pref_hor[i+R-1][j];
        pref_ver[0][j] = 0;
    }
    short res = 0;
    for (int i = 1; i + R-1 <= m; i++)
        for (int j = 1; j + R-1 <= m; j++)
            maximize(res, pref_ver[i][j]);
    printf("%d\n", int(res));
    return 0;
}

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define maximize(__x,__y) __x=max(__x,__y)
#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 5100;

int n, R;
int arr[maxn][maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &R);
    for (int i = 1, a, b, c; i <= n; i++) {
        scanf("%d%d%d", &a, &b, &c);
        arr[a+1][b+1] += c;
    }
    int m = 5001;
    rep(i, 1, m) rep(j, 1, m)
        arr[i][j] += arr[i][j - 1];
    rep(j, 1, m) rep(i, 1, m)
        arr[i][j] += arr[i - 1][j];
    int res = 0;
    rep(i, R, m) rep(j, R, m)
        maximize(res, arr[i][j] + arr[i-R][j-R] - arr[i][j-R] - arr[i-R][j]);
    printf("%d\n", res);
    return 0;
}