結果

問題 No.3509 Get More Money
コンテスト
ユーザー Naru820
提出日時 2026-04-14 15:04:24
言語 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,185 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,052 ms
コンパイル使用メモリ 340,668 KB
実行使用メモリ 21,632 KB
最終ジャッジ日時 2026-04-17 20:13:52
合計ジャッジ時間 18,843 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 30 WA * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

using ll = long long;

struct Solver {
    map<ll, ll> mp;   // value -> count
    ll sz = 0;        // total count in mp
    ll ans = 0;       // current maximum profit with 0 jewels

    void add_value(ll v, ll c) {
        if (c == 0) return;
        mp[v] += c;
        sz += c;
    }

    // Remove k smallest values and return their sum
    ll remove_smallest(ll k) {
        ll sum = 0;
        while (k > 0) {
            auto it = mp.begin();
            ll v = it->first;
            ll c = it->second;
            ll take = min(k, c);
            sum += v * take;
            sz -= take;
            k -= take;
            if (take == c) mp.erase(it);
            else it->second -= take;
        }
        return sum;
    }

    // Remove k largest values
    void remove_largest(ll k) {
        while (k > 0) {
            auto it = prev(mp.end());
            ll c = it->second;
            ll take = min(k, c);
            sz -= take;
            k -= take;
            if (take == c) mp.erase(it);
            else it->second -= take;
        }
    }

    ll solve_case(int N, ll K,
                  const vector<ll>& A,
                  const vector<ll>& B,
                  const vector<ll>& C,
                  const vector<ll>& D) {
        mp.clear();
        sz = 0;
        ans = 0;

        for (int i = 0; i < N; ++i) {
            add_value(A[i], B[i]);
            add_value(C[i], D[i]);

            ll s = remove_smallest(D[i]);
            ans += C[i] * D[i] - s;

            if (sz > K) {
                remove_largest(sz - K);
            }
        }

        return ans;
    }
};

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

    int T;
    cin >> T;

    Solver solver;

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

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

        cout << solver.solve_case(N, K, A, B, C, D) << ' ';
    }

    return 0;
}
0