結果

問題 No.2741 Balanced Choice
ユーザー Ryoga.exeRyoga.exe
提出日時 2024-04-21 04:15:26
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 51 ms / 2,000 ms
コード長 3,170 bytes
コンパイル時間 3,188 ms
コンパイル使用メモリ 257,160 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-13 02:39:58
合計ジャッジ時間 3,775 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 49 ms
6,820 KB
testcase_01 AC 51 ms
6,816 KB
testcase_02 AC 50 ms
6,816 KB
testcase_03 AC 50 ms
6,816 KB
testcase_04 AC 51 ms
6,816 KB
testcase_05 AC 1 ms
6,816 KB
testcase_06 AC 2 ms
6,820 KB
testcase_07 AC 32 ms
6,816 KB
testcase_08 AC 43 ms
6,816 KB
testcase_09 AC 31 ms
6,816 KB
testcase_10 AC 34 ms
6,820 KB
testcase_11 AC 43 ms
6,816 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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) {
                        nxt[j] = dp[p][j];
                        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 (rw < i - d) {
            continue;
        }
        // i - d <= 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);
    }
    cout << ans << endl;
    return 0;
}
0