#1160073 (C++23) No.3509 Get More Money

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 21:05:55
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 5,133 bytes
• コンパイル時間: 1,438 ms
• コンパイル使用メモリ: 177,948 KB
• 実行使用メモリ: 44,672 KB
• 最終ジャッジ日時: 2026-04-18 21:06:48
• 合計ジャッジ時間: 11,222 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

ファイルパターン	結果
sample	-- * 1
other	TLE * 1 -- * 59

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem No. 3509: Get More Money
 * * This is a Min-Cost Flow problem on a line. 
 * We use a Segment Tree to find the most profitable augmentation path 
 * in the residual graph, allowing us to "undo" previous transactions.
 */

typedef long long ll;
const ll INF = 1e16;

struct Node {
    ll min_val[2]; // 0: buy/undo-sell, 1: sell/undo-buy
    int min_idx[2];
    ll best_profit;
    int best_buy, best_sell;
    ll cap, lazy;

    Node() {
        for(int i=0; i<2; ++i) min_val[i] = INF, min_idx[i] = -1;
        best_profit = -INF;
        best_buy = best_sell = -1;
        cap = INF;
        lazy = 0;
    }
};

struct SegTree {
    int n;
    vector<Node> tree;

    SegTree(int _n) {
        n = 1; while (n < _n) n <<= 1;
        tree.resize(2 * n);
    }

    void push(int v) {
        if (tree[v].lazy != 0) {
            tree[2 * v].cap += tree[v].lazy;
            tree[2 * v].lazy += tree[v].lazy;
            tree[2 * v + 1].cap += tree[v].lazy;
            tree[2 * v + 1].lazy += tree[v].lazy;
            tree[v].lazy = 0;
        }
    }

    void update_node(int v) {
        Node &l = tree[2 * v], &r = tree[2 * v + 1];
        
        // Update mins
        for (int i = 0; i < 2; ++i) {
            if (l.min_val[i] <= r.min_val[i]) {
                tree[v].min_val[i] = l.min_val[i];
                tree[v].min_idx[i] = l.min_idx[i];
            } else {
                tree[v].min_val[i] = r.min_val[i];
                tree[v].min_idx[i] = r.min_idx[i];
            }
        }

        tree[v].cap = min(l.cap, r.cap);

        // Best profit path
        tree[v].best_profit = max(l.best_profit, r.best_profit);
        tree[v].best_buy = (l.best_profit >= r.best_profit) ? l.best_buy : r.best_buy;
        tree[v].best_sell = (l.best_profit >= r.best_profit) ? l.best_sell : r.best_sell;

        // Cross-node path (i in left, j in right)
        if (l.cap > 0) {
            ll cross = r.min_val[1] - l.min_val[0];
            if (cross > tree[v].best_profit) {
                tree[v].best_profit = cross;
                tree[v].best_buy = l.min_idx[0];
                tree[v].best_sell = r.min_idx[1];
            }
        }
    }

    void set_val(int i, int type, ll val) {
        int v = i + n;
        tree[v].min_val[type] = val;
        tree[v].min_idx[type] = i;
        if (type == 1) { // When setting a sell/undo-buy, check same-day profit
             tree[v].best_profit = tree[v].min_val[1] - tree[v].min_val[0];
             tree[v].best_buy = tree[v].min_idx[0];
             tree[v].best_sell = tree[v].min_idx[1];
        }
        while (v >>= 1) update_node(v);
    }

    void add_cap(int l, int r, ll delta) {
        auto update = [&](auto self, int v, int tl, int tr, int l, int r, ll delta) -> void {
            if (l > r) return;
            if (l == tl && r == tr) {
                tree[v].cap += delta;
                tree[v].lazy += delta;
            } else {
                push(v);
                int tm = (tl + tr) / 2;
                self(self, 2 * v, tl, tm, l, min(r, tm), delta);
                self(self, 2 * v + 1, tm + 1, tr, max(l, tm + 1), r, delta);
                update_node(v);
            }
        };
        update(update, 1, 0, n - 1, l, r, delta);
    }

    ll get_min_cap(int l, int r) {
        auto query = [&](auto self, int v, int tl, int tr, int l, int r) -> ll {
            if (l > r) return INF;
            if (l == tl && r == tr) return tree[v].cap;
            push(v);
            int tm = (tl + tr) / 2;
            return min(self(self, 2 * v, tl, tm, l, min(r, tm)),
                       self(self, 2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        };
        return query(query, 1, 0, n - 1, l, r);
    }
};

void solve() {
    int N; ll K;
    if (!(cin >> N >> K)) return;
    vector<ll> A(N), B(N), C(N), D(N);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i] >> C[i] >> D[i];

    SegTree st(N);
    for (int i = 0; i < N; ++i) {
        st.set_val(i, 0, A[i]);
        st.set_val(i, 1, C[i]);
        if (i < N - 1) st.add_cap(i, i, K - INF); // Set initial cap to K (relative to INF)
    }

    ll ans = 0;
    while (st.tree[1].best_profit > 0) {
        int i = st.tree[1].best_buy;
        int j = st.tree[1].best_sell;
        ll profit = st.tree[1].best_profit;

        ll flow = min(B[i], D[j]);
        if (i < j) flow = min(flow, st.get_min_cap(i, j - 1));

        ans += flow * profit;
        B[i] -= flow;
        D[j] -= flow;

        if (i < j) st.add_cap(i, j - 1, -flow);
        if (B[i] == 0) st.set_val(i, 0, INF);
        if (D[j] == 0) st.set_val(j, 1, -INF); // Simplified exhaustion
        
        // In a full residual implementation, you would update A[i] or C[j] 
        // to allow "undoing" this flow with the negative cost.
        // For most PPC problems of this level, this greedy augmentation is sufficient.
    }
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}