#976091 (C++23) No.2741 Balanced Choice

• 問題: No.2741 Balanced Choice
• ユーザー: Ryoga.exe
• 提出日時: 2024-04-21 03:53:59
• 言語: C++23 (gcc 13.3.0 + boost 1.87.0)
• 結果: WA
• 実行時間: -
• コード長: 3,418 bytes
• コンパイル時間: 5,357 ms
• コンパイル使用メモリ: 256,540 KB
• 実行使用メモリ: 6,824 KB
• 最終ジャッジ日時: 2024-10-13 02:15:22
• 合計ジャッジ時間: 3,916 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 2
other	WA * 10

ソースコード

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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class S, auto op, auto e> struct SegmentTree {
  public:
    SegmentTree() : SegmentTree(0) {}
    explicit SegmentTree(const size_t n) : SegmentTree(vector<S>(n, e())) {}
    explicit SegmentTree(const vector<S> &v) : m_size(v.size()) {
        for (m_leafSize = 1; m_leafSize < m_size;) {
            m_leafSize <<= 1;
        }
        m_data.assign(2 * m_leafSize, e());
        for (int i = 0; i < m_size; i++) {
            m_data[m_leafSize + i] = v[i];
        }
        for (int i = m_leafSize - 1; i >= 1; i--) {
            m_data[i] = op(m_data[2 * i], m_data[2 * i + 1]);
        }
    }
    void set(size_t p, const S &x) {
        assert(0 <= p && p < m_size);
        p += m_leafSize;
        m_data[p] = x;
        update(p);
    }
    void add(size_t p, const S &x) {
        assert(0 <= p && p < m_size);
        p += m_leafSize;
        m_data[p] += x;
        update(p);
    }
    S prod(size_t l, size_t r) const {
        assert(0 <= l && l <= r && r <= m_size);
        auto sml = e(), smr = e();
        for (l += m_leafSize, r += m_leafSize; l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                sml = op(sml, m_data[l++]);
            }
            if (r & 1) {
                smr = op(m_data[--r], smr);
            }
        }
        return op(sml, smr);
    }
    inline S allProd() const { return m_data[1]; }
  private:
    size_t m_size;
    size_t m_leafSize = 1;
    vector<S> m_data;
    inline void update(size_t p) {
        while (p >>= 1) {
            m_data[p] = op(m_data[2 * p], m_data[2 * p + 1]);
        }
    }
};
using RMQ = SegmentTree<ll, [](ll a, ll b) { return max(a, b); },
                        []() { return numeric_limits<ll>::lowest(); }>;
int main() {
    int n, w, d;
    cin >> n >> w >> d;
    vector<pair<ll, ll>> t[2];
    for (int i = 0; i < n; i++) {
        ll ti, wi, vi;
        cin >> ti >> wi >> vi;
        t[ti].emplace_back(wi, vi);
    }
    vector dp(2, vector(w + 1, -1ll));
    dp[0][0] = dp[1][0] = 0;
    for (const auto p : {0, 1}) {
        const auto &v = t[p];
        for (int i = 0; i < v.size(); i++) {
            const auto [wi, vi] = v[i];
            auto nxt = vector(w + 1, -1ll);
            for (int j = 0; j <= w; j++) {
                if (j - wi >= 0) {
                    if (dp[p][j - wi] == -1) {
                        continue;
                    }
                    nxt[j] = max(dp[p][j - wi] + vi, dp[p][j]);
                } else {
                    nxt[j] = dp[p][j];
                }
            }
            swap(dp[p], nxt);
        }
    }
    RMQ segtree(dp[1]);
    ll ans = 0;
    for (int i = 0; i <= w; i++) {
        if (dp[0][i] == -1) {
            continue;
        }
        const auto rw = w - i;
        if (i <= rw) {
            const auto cur = segtree.prod(max(0, i - d), min(i + d, rw) + 1);
            if (cur == -1) {
                continue;
            }
            ans = max(ans, dp[0][i] + cur);
        } else {
            // rw < i
            if (rw < i - d) {
                continue;
            }
            // i - d <= rw < i
            const auto cur = segtree.prod(max(0, i - d), rw + 1);
            if (cur == -1) {
                continue;
            }
            ans = max(ans, dp[0][i] + cur);
        }
    }
    cout << ans << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX