結果

問題 No.3509 Get More Money
コンテスト
ユーザー Naru820
提出日時 2026-04-07 12:16:00
言語 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
結果
WA  
実行時間 -
コード長 2,226 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,091 ms
コンパイル使用メモリ 176,172 KB
実行使用メモリ 15,744 KB
最終ジャッジ日時 2026-04-17 20:05:49
合計ジャッジ時間 16,102 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using namespace std;

void solve() {
    int N;
    long long K;
    cin >> N >> K;

    // {傾き(限界価値), その個数} を管理するマップ
    map<long long, long long> mp;
    long long total_count = 0; // 現在マップに入っている要素の総数
    long long profit = 0;      // 確定した純利益

    for (int i = 0; i < N; ++i) {
        long long A, B, C, D;
        cin >> A >> B >> C >> D;

        // 1. ジュエルを買う
        if (B > 0) {
            mp[-A] += B;
            total_count += B;
        }

        // 2. ジュエルを売る
        long long count_to_add = 0;
        while (D > 0 && !mp.empty()) {
            // 最も価値の高い（傾きが最大の）ジュエルを取得
            auto it = prev(mp.end());
            long long s = it->first;
            long long cnt = it->second;

            // 利益が出ないならこれ以上売らない
            if (s <= -C) break;

            long long use = min(D, cnt);
            profit += use * (s + C);
            count_to_add += use;
            D -= use;

            // マップの更新（使い切った要素は削除）
            if (use == cnt) {
                mp.erase(it);
            } else {
                it->second -= use;
            }
        }
        
        // 売却のキャンセル権（傾き -C）を追加
        if (count_to_add > 0) {
            mp[-C] += count_to_add;
        }

        // 3. 保管庫の容量制限 (K個まで)
        while (total_count > K) {
            // 最も価値の低い（傾きが最小の）ジュエルから捨てる
            auto it = mp.begin();
            if (it->second <= total_count - K) {
                total_count -= it->second;
                mp.erase(it);
            } else {
                it->second -= (total_count - K);
                total_count = K;
            }
        }
    }

    cout << profit << "\n";
}

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