#1191915 (C++23(gcc16)) No.3764 Graduation Live

• 問題: No.3764 Graduation Live
• ユーザー: ei13333333
• 提出日時: 2026-10-08 00:16:35
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: TLE
• 実行時間: -
• コード長: 4,544 bytes
• コンパイル時間: 2,634 ms
• コンパイル使用メモリ: 367,456 KB
• 実行使用メモリ: 9,904 KB
• 最終ジャッジ日時: 2026-10-09 20:55:43
• 合計ジャッジ時間: 46,510 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge5_0

ファイルパターン	結果
sample	AC * 3
other	AC * 40 TLE * 5

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct Delta {
    int8_t d[6];        // count の変化量
    int8_t du[3];       // stamina 使用量の変化量
    uint8_t changed[6]; // d[t] != 0 の t
    uint8_t m;
};

const vector<Delta>& get_deltas() {
    static const vector<Delta> ds = [] {
        vector<Delta> res;
        int d[6];

        auto dfs = [&](auto&& self, int i, int sum, int removed) -> void {
            if (i == 6) {
                if (sum != 1 || removed > 2) return;

                Delta x{};
                for (int t = 0; t < 6; ++t) {
                    x.d[t] = d[t];
                    if (d[t] != 0)
                        x.changed[x.m++] = t;
                }

                x.du[0] = d[0] + d[3] + d[4];
                x.du[1] = d[1] + d[3] + d[5];
                x.du[2] = d[2] + d[4] + d[5];

                res.push_back(x);
                return;
            }

            // remove <= 2 なので各成分は [-2, 3] だけ見ればよい。
            for (int x = -2; x <= 3; ++x) {
                int nr = removed + max(0, -x);
                if (nr > 2) continue;

                d[i] = x;
                self(self, i + 1, sum + x, nr);
            }
        };

        dfs(dfs, 0, 0, 0);
        return res;
    }();

    return ds;
}

void solve() {
    int n;
    int stamina[3];
    cin >> n >> stamina[0] >> stamina[1] >> stamina[2];

    array<vector<ll>, 6> value;

    for (int i = 0; i < n; ++i) {
        int t;
        ll v;
        cin >> t >> v;
        value[t - 1].push_back(v);
    }

    int sz[6];

    for (int t = 0; t < 6; ++t) {
        sort(value[t].rbegin(), value[t].rend());
        sz[t] = value[t].size();
    }

    const auto& deltas = get_deltas();

    int cnt[6] = {};
    int used[3] = {};
    ll score = 0;

    vector<ll> ans;
    ans.reserve(n);

    for (int depth = 1; depth <= n; ++depth) {
        const Delta* best = nullptr;
        ll best_score = LLONG_MIN;

        // deltas は d[0], d[1], ... の辞書順で生成される。
        //
        // 元コードの key も count[0], count[1], ... の辞書順なので、
        // score が同じなら「最初に見つけた候補」を残すだけで
        // 元の tie-break と一致する。
        for (const Delta& x : deltas) {
            if (used[0] + x.du[0] > stamina[0] ||
                used[1] + x.du[1] > stamina[1] ||
                used[2] + x.du[2] > stamina[2])
                continue;

            ll s = score;
            bool ok = true;

            // 変化する type だけ見る。
            for (int j = 0; j < x.m; ++j) {
                int t = x.changed[j];
                int c = cnt[t];
                int d = x.d[t];

                int nc = c + d;

                // 0 <= nc <= sz[t]
                if ((unsigned)nc > (unsigned)sz[t]) {
                    ok = false;
                    break;
                }

                // prefix sum すら不要。
                // 境界で増減する要素だけ直接加減する。
                switch (d) {
                    case 1:
                        s += value[t][c];
                        break;

                    case 2:
                        s += value[t][c]
                           + value[t][c + 1];
                        break;

                    case 3:
                        s += value[t][c]
                           + value[t][c + 1]
                           + value[t][c + 2];
                        break;

                    case -1:
                        s -= value[t][c - 1];
                        break;

                    case -2:
                        s -= value[t][c - 1]
                           + value[t][c - 2];
                        break;
                }
            }

            if (!ok) continue;

            if (!best || s > best_score) {
                best = &x;
                best_score = s;
            }
        }

        if (!best) break;

        for (int j = 0; j < best->m; ++j) {
            int t = best->changed[j];
            cnt[t] += best->d[t];
        }

        used[0] += best->du[0];
        used[1] += best->du[1];
        used[2] += best->du[2];

        score = best_score;
        ans.push_back(score);
    }

    cout << ans.size();
    for (ll x : ans)
        cout << ' ' << x;
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--)
        solve();
}