#995151 (C++17) No.2859 Falling Balls

• 問題: No.2859 Falling Balls
• ユーザー: square1001
• 提出日時: 2024-07-15 12:00:39
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 1,935 bytes
• コンパイル時間: 1,187 ms
• コンパイル使用メモリ: 88,196 KB
• 最終ジャッジ日時: 2025-02-23 15:45:39
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
other	AC * 26 WA * 4

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const long long INF = 3LL << 59;
class segment_tree {
private:
    int size;
    vector<long long> v;
public:
    segment_tree() : size(0), v() {}
    segment_tree(int n) : size(1 << (n >= 2 ? 32 - __builtin_clz(n - 1) : 0)), v(vector<long long>(size * 2, -INF)) {}
    void update(int pos, long long x) {
        pos += size;
        v[pos] = x;
        while (pos > 1) {
            pos /= 2;
            v[pos] = max(v[pos * 2 + 0], v[pos * 2 + 1]);
        }
    }
    long long range_max(int l, int r) {
        l += size;
        r += size;
        long long z = -INF;
        while (l != r) {
            if (l & 1) z = max(z, v[l++]);
            if (r & 1) z = max(z, v[--r]);
            l /= 2;
            r /= 2;
        }
        return z;
    }
};
int main() {
    // step #1. input
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int N; long long K;
    cin >> N >> K;
    vector<long long> T(N), X(N), C(N);
    for (int i = 0; i < N; i++) {
        cin >> T[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> X[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> C[i];
    }
    // step #2. preparation
    vector<long long> PX(N), PY(N);
    for (int i = 0; i < N; i++) {
        PX[i] = T[i] * K - X[i];
        PY[i] = T[i] * K + X[i];
    }
    vector<long long> SY = PY;
    SY.push_back(0);
    sort(SY.begin(), SY.end());
    SY.erase(unique(SY.begin(), SY.end()), SY.end());
    int Z = SY.size();
    vector<int> perm(N);
    for (int i = 0; i < N; i++) {
        perm[i] = i;
    }
    sort(perm.begin(), perm.end(), [&](int a, int b) {
        return make_pair(PX[a], PY[a]) < make_pair(PX[b], PY[b]);
    });
    // step #3. dynamic programming
    segment_tree seg(Z);
    int base_pos = lower_bound(SY.begin(), SY.end(), 0) - SY.begin();
    seg.update(base_pos, 0);
    for (int i : perm) {
        int pos = lower_bound(SY.begin(), SY.end(), PY[i]) - SY.begin();
        long long x = seg.range_max(0, pos + 1);
        if (x != -INF) {
            seg.update(pos, x + C[i]);
        }
    }
    // step #4. get answer & output
    long long ans = seg.range_max(0, Z);
    cout << ans << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX