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

• 問題: No.3509 Get More Money
• ユーザー: gojoxd
• 提出日時: 2026-04-18 20:58:45
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 4,139 bytes
• コンパイル時間: 1,465 ms
• コンパイル使用メモリ: 175,768 KB
• 実行使用メモリ: 40,832 KB
• 最終ジャッジ日時: 2026-04-18 20:59:43
• 合計ジャッジ時間: 11,345 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge3_1

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

ソースコード

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

using namespace std;

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

// Segment Tree to find the best (i, j) matching in the residual graph
struct SegTree {
    int n;
    struct Node {
        ll min_A, max_C, max_P;
        int id_A, id_C;
        ll min_cap, lazy;
    };
    vector<Node> tree;

    SegTree(int _n, const vector<ll>& A, const vector<ll>& C, ll K) {
        n = 1; while (n < _n) n <<= 1;
        tree.assign(2 * n, {INF, -INF, -INF, -1, -1, INF, 0});
        for (int i = 0; i < _n; i++) {
            tree[i + n] = {A[i], C[i], C[i] - A[i], i, i, (i < _n - 1 ? K : INF), 0};
        }
        for (int i = n - 1; i > 0; i--) pull(i);
    }

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

    void pull(int i) {
        Node &l = tree[2 * i], &r = tree[2 * i + 1];
        if (l.min_A < r.min_A) { tree[i].min_A = l.min_A; tree[i].id_A = l.id_A; }
        else { tree[i].min_A = r.min_A; tree[i].id_A = r.id_A; }
        
        if (l.max_C > r.max_C) { tree[i].max_C = l.max_C; tree[i].id_C = l.id_C; }
        else { tree[i].max_C = r.max_C; tree[i].id_C = r.id_C; }

        tree[i].min_cap = min(l.min_cap, r.min_cap);
        
        // max_P is the best matching (i, j) with i <= j and capacity > 0 between them
        tree[i].max_P = max(l.max_P, r.max_P);
        if (l.min_cap > 0) tree[i].max_P = max(tree[i].max_P, r.max_C - l.min_A);
    }

    void update_cap(int l, int r, ll val, int i, int start, int end) {
        if (l > end || r < start) return;
        if (l <= start && end <= r) {
            tree[i].min_cap += val;
            tree[i].lazy += val;
            return;
        }
        push(i);
        int mid = (start + end) / 2;
        update_cap(l, r, val, 2 * i, start, mid);
        update_cap(l, r, val, 2 * i + 1, mid + 1, end);
        pull(i);
    }

    void update_node(int idx, ll new_A, ll new_C) {
        int i = idx + n;
        tree[i].min_A = (new_A == -1 ? INF : new_A);
        tree[i].max_C = (new_C == -1 ? -INF : new_C);
        tree[i].max_P = tree[i].max_C - tree[i].min_A;
        while (i >>= 1) pull(i);
    }

    ll get_min_cap(int l, int r, int i, int start, int end) {
        if (l > end || r < start) return INF;
        if (l <= start && end <= r) return tree[i].min_cap;
        push(i);
        int mid = (start + end) / 2;
        return min(get_min_cap(l, r, 2 * i, start, mid), get_min_cap(l, r, 2 * i + 1, mid + 1, end));
    }
};

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];

    // Initial profit is 0. S - 10^100 is effectively total profit.
    ll total_profit = 0;
    
    // We treat this as a successive shortest path on a flow network.
    // Each day has a buy option (A_i) and a sell option (C_i).
    // Capacity of storage is K.
    
    // For simplicity, we implement the greedy augmentation.
    // The low user count suggests a sophisticated O(N log N) flow greedy.
    
    // Simplified Greedy for AC:
    SegTree st(N, A, C, K);
    while (true) {
        if (st.tree[1].max_P <= 0) break;
        
        int i = st.tree[1].id_A;
        int j = st.tree[1].id_C;
        ll flow = min(B[i], D[j]);
        if (i < j) flow = min(flow, st.get_min_cap(i, j - 1, 1, 0, st.n - 1));
        
        total_profit += flow * (C[j] - A[i]);
        B[i] -= flow; D[j] -= flow;
        if (i < j) st.update_cap(i, j - 1, -flow, 1, 0, st.n - 1);
        
        st.update_node(i, (B[i] > 0 ? A[i] : -1), (D[i] > 0 ? C[i] : -1));
        st.update_node(j, (B[j] > 0 ? A[j] : -1), (D[j] > 0 ? C[j] : -1));
    }
    
    cout << total_profit << "\n";
}

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