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

• 問題: No.3764 Graduation Live
• ユーザー: ei13333333
• 提出日時: 2026-10-09 00:11:59
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: RE
• 実行時間: -
• コード長: 5,419 bytes
• コンパイル時間: 2,823 ms
• コンパイル使用メモリ: 372,476 KB
• 実行使用メモリ: 9,924 KB
• 最終ジャッジ日時: 2026-10-09 20:56:16
• 合計ジャッジ時間: 12,012 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge4_0

ファイルパターン	結果
sample	RE * 3
other	AC * 2 RE * 43

ソースコード

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

#define FOR(i, n, m) for (int i = n; i < (int)m; ++i)
#define REP(i, n) FOR(i, 0, n)
#define REP_1(i, n) for (int i = 1; i <= (int)n; ++i)
#define RFOR(i, n, m) for (int i = (int)n - 1; i >= (int)m; --i)
#define RREP(i, n) RFOR(i, n, 0)
#define RREP_1(i, n) for (int i = (int)n; i >= 1; --i)

#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define SIZE(v) (int)v.size()
#define EMPTY(v) v.empty()
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(RALL(v))
#define REVERSE(v) reverse(ALL(v))
#define UNIQUE(v) (SORT(v), v.erase(unique(ALL(v)), v.end()))

#define PB push_back
#define EB emplace_back
#define MP make_pair

#define YES() cout << "YES\n"
#define NO() cout << "NO\n"
#define Yes() cout << "Yes\n"
#define No() cout << "No\n"
#define YESNO(cond) cout << ((cond) ? "YES" : "NO") << '\n'
#define YesNo(cond) cout << ((cond) ? "Yes" : "No") << '\n'

#define IN(x, a, b) ((a) <= (x) && (x) < (b))
#define BETWEEN(x, a, b) ((a) <= (x) && (x) <= (b))

#define FASTIO()                                                               \
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define PRECISION(n) cout << fixed << setprecision(n)

using P = pair<int, int>;
using ll = long long;
using ull = unsigned long long;
using ld = long double;

template <class T> using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T> using max_queue = priority_queue<T>;

constexpr ll INF = 1000000000;
constexpr ll INFL = (ll)1000000000000001000LL;
constexpr ll MOD = 998244353;
constexpr ld PI = 3.141592653589793238462643383279;
constexpr ld EPS = 1e-9;

struct edge {
    int to;
    int cap;
    ll cost;
    int rev;
    bool isrev;
    int song = -1;
};

void solve() {
    int n, y, k, i;
    cin >> n >> y >> k >> i;
    vector<vector<int>> values(6);
    vector<P> pairs = {{0, 1}, {0, 2}, {0, 3}, {1, 2}, {1, 3}, {2, 3}};
    REP(i, n) {
        int t, v;
        cin >> t >> v;
        values[t].PB(v);
    }
    REP(i, 6) RSORT(values[i]);
    vector<ll> ans;

    const int V = 10, S = 8, T = 9;
    vector<vector<edge>> graph(V);
    auto add_edge = [&](int from, int to, int cap, ll cost, int song = -1) {
        int idx = SIZE(graph[from]);
        graph[from].PB((edge){to, cap, cost, SIZE(graph[to]), false, song});
        graph[to].PB((edge){from, 0, -cost, idx, true, song});
        return idx;
    };
    vector<int> caps = {n, y, k, i};
    REP(j, 4) {
        add_edge(S, j, caps[j], 0);
        add_edge(j + 4, T, caps[j], 0);
    }
    vector<P> song_edges(12);
    vector<int> used(12, 0);
    REP(t, 6) REP(d, 2) {
        int from = d ? pairs[t].second : pairs[t].first;
        int to = (d ? pairs[t].first : pairs[t].second) + 4;
        song_edges[2 * t + d] = {from, add_edge(from, to, 0, 0, 2 * t + d)};
    }
    auto update_song_edges = [&]() {
        REP(id, 12) {
            auto [from, idx] = song_edges[id];
            edge &e = graph[from][idx];
            edge &r = graph[e.to][e.rev];
            auto &vs = values[id / 2];
            int u = used[id];
            e.cap = u < SIZE(vs);
            e.cost = e.cap ? -ll(vs[u]) : 0;
            r.cap = u > 0;
            r.cost = r.cap ? ll(vs[u - 1]) : 0;
        }
    };
    update_song_edges();

    vector<ll> potential, min_cost;
    vector<int> prevv, preve;
    using Pi = pair<ll, int>;
    priority_queue<Pi, vector<Pi>, greater<Pi>> que;
    potential.assign(V, 0);
    REP(step, V - 1) REP(v, V) {
        for (auto &e : graph[v]) {
            if (e.cap > 0)
                potential[e.to] = min(potential[e.to], potential[v] + e.cost);
        }
    }
    ll ret = 0;
    int flow = 0;
    while (true) {
        min_cost.assign(V, INFL);
        min_cost[S] = 0;
        que.emplace(0, S);
        preve.assign(V, -1);
        prevv.assign(V, -1);
        while (!que.empty()) {
            Pi p = que.top();
            que.pop();
            if (min_cost[p.second] < p.first) continue;
            for (int i = 0; i < (int)graph[p.second].size(); i++) {
                edge &e = graph[p.second][i];
                ll nextCost = min_cost[p.second] + e.cost +
                              potential[p.second] - potential[e.to];
                if (e.cap > 0 && min_cost[e.to] > nextCost) {
                    min_cost[e.to] = nextCost;
                    prevv[e.to] = p.second, preve[e.to] = i;
                    que.emplace(min_cost[e.to], e.to);
                }
            }
        }
        if (min_cost[T] == INFL) break;
        for (int v = 0; v < V; v++)
            if (min_cost[v] != INFL) potential[v] += min_cost[v];
        int addflow = 1;
        for (int v = T; v != S; v = prevv[v]) {
            addflow = std::min(addflow, graph[prevv[v]][preve[v]].cap);
        }
        ret += addflow * (potential[T] - potential[S]);
        for (int v = T; v != S; v = prevv[v]) {
            edge &e = graph[prevv[v]][preve[v]];
            e.cap -= addflow;
            graph[v][e.rev].cap += addflow;
            if (e.song != -1) used[e.song] += e.isrev ? -1 : 1;
        }
        update_song_edges();
        flow += addflow;
        if (flow % 2 == 0) ans.PB(-ret / 2);
    }

    cout << ans.size() << " ";
    REP(i, ans.size()) cout << ans[i] << " ";
    cout << endl;
}

int main() {
    FASTIO();
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
}