結果

問題 No.3509 Get More Money
コンテスト
ユーザー e032_Ashmit_Rana
提出日時 2026-04-18 01:14:04
言語 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  
実行時間 138 ms / 2,000 ms
コード長 1,725 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,353 ms
コンパイル使用メモリ 341,392 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2026-04-18 01:14:24
合計ジャッジ時間 12,932 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 60
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int N;
        int64 K;
        cin >> N >> K;

        vector<int64> A(N), B(N), C(N), D(N);
        for (auto &x : A) cin >> x;
        for (auto &x : B) cin >> x;
        for (auto &x : C) cin >> x;
        for (auto &x : D) cin >> x;

        map<int64, int64> slopes;
        int64 slope_count = 0;
        int64 answer = 0;

        auto add_slope = [&](int64 slope, int64 count) {
            if (count <= 0) return;
            slopes[slope] += count;
            slope_count += count;
        };

        auto erase_from_iterator = [&](map<int64, int64>::iterator it, int64 count) {
            it->second -= count;
            slope_count -= count;
            if (it->second == 0) slopes.erase(it);
        };

        for (int i = 0; i < N; i++) {
            add_slope(-A[i], B[i]);

            int64 remaining = D[i];
            while (remaining > 0 && !slopes.empty()) {
                auto it = prev(slopes.end());
                int64 best = it->first;
                if (best + C[i] <= 0) break;

                int64 take = min(remaining, it->second);
                answer += take * (best + C[i]);
                erase_from_iterator(it, take);
                add_slope(-C[i], take);
                remaining -= take;
            }

            while (slope_count > K) {
                auto it = slopes.begin();
                int64 drop = min(slope_count - K, it->second);
                erase_from_iterator(it, drop);
            }
        }

        cout << answer << '\n';
    }

    return 0;
}
0