結果

問題 No.3509 Get More Money
コンテスト
ユーザー Naru820
提出日時 2026-03-17 22:50:50
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 204 ms / 2,000 ms
コード長 2,703 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,193 ms
コンパイル使用メモリ 179,308 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2026-04-17 19:41:32
合計ジャッジ時間 12,421 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//gemini3.1pro
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

void solve() {
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> A(n), B(n), C(n), D(n);
    for (int i = 0; i < n; i++) cin >> A[i];
    for (int i = 0; i < n; i++) cin >> B[i];
    for (int i = 0; i < n; i++) cin >> C[i];
    for (int i = 0; i < n; i++) cin >> D[i];

    // 売却の選択肢を管理するプール {価格, 個数}
    map<long long, long long> pool;
    long long total_pool = 0;
    long long max_profit = 0;

    // 後ろの日付から逆順に処理
    for (int i = n - 1; i >= 0; i--) {
        // 1. その日の売却枠をプールに追加
        if (D[i] > 0) {
            pool[C[i]] += D[i];
            total_pool += D[i];
        }

        // 2. その日の購入枠を使って、最も高い売却枠と貪欲にマッチング
        long long to_buy = B[i];
        long long matched = 0;
        
        while (to_buy > 0 && !pool.empty()) {
            auto it = prev(pool.end()); // 最も価格が高い選択肢
            long long price = it->first;
            long long count = it->second;

            // 利益が出ないなら終了
            if (price <= A[i]) break;

            long long take = min(to_buy, count);
            max_profit += take * (price - A[i]);
            matched += take;
            to_buy -= take;
            total_pool -= take;

            if (count == take) {
                pool.erase(it);
            } else {
                it->second -= take;
            }
        }

        // マッチングした分だけ「キャンセル権」として A[i] の売却枠を追加
        if (matched > 0) {
            pool[A[i]] += matched;
            total_pool += matched;
        }

        // 3. 前日に持ち越せるのは最大 K 個なので、安い選択肢から捨てる
        while (total_pool > k && !pool.empty()) {
            auto it = pool.begin(); // 最も価格が安い選択肢
            long long count = it->second;
            long long excess = total_pool - k;

            if (count <= excess) {
                total_pool -= count;
                pool.erase(it);
            } else {
                it->second -= excess;
                total_pool -= excess;
                break;
            }
        }
    }

    // 最初から 10^100 ゴールド持っている前提で増えた分だけ出力
    cout << max_profit << "\n";
}

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}
0