Submission #1200580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200580		pinbu	Shopping Plans (CCO20_day2problem3)	C++20	0 / 25	8 ms	1348 KiB

Main

// not by me :P

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

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

    int N, M, K;
    if(!(cin >> N >> M >> K)) return 0;
    vector<vector<ll>> costs(M + 1);
    for(int i = 0; i < N; i++){
        int a;
        ll c;
        cin >> a >> c;
        costs[a].push_back(c);
    }
    vector<int> x(M + 1), y(M + 1);
    for(int j = 1; j <= M; j++){
        cin >> x[j] >> y[j];
    }
    
    // 1) sort and prefix sums
    vector<ll> base_pref(M + 1, 0);
    ll base_cost = 0;
    vector<vector<ll>> extra(M + 1);
    for(int j = 1; j <= M; j++){
        auto &v = costs[j];
        sort(v.begin(), v.end());
        int need = x[j];
        if((int)v.size() < need){
            // not enough items -> no feasible plans
            for(int i = 0; i < K; i++) cout << -1 << '\n';
            return 0;
        }
        // compute prefix
        vector<ll> pref(v.size() + 1, 0);
        for(size_t i = 1; i < pref.size(); i++) pref[i] = pref[i-1] + v[i-1];
        base_cost += pref[need];
        // build extra costs d_j[k] = pref[need + k] - pref[need], for k=0..(y[j]-need)
        int maxk = min((ll)y[j] - need, (ll)v.size() - need);
        extra[j].reserve(maxk + 1);
        for(int k = 0; k <= maxk; k++){
            extra[j].push_back(pref[need + k] - pref[need]);
        }
        // already sorted by construction
    }

    // merge function: K smallest sums of sorted A and B
    auto mergeK = [&](const vector<ll> &A, const vector<ll> &B){
        int n = A.size(), m = B.size();
        vector<ll> C;
        C.reserve(min((ll)K, (ll)n * m));
        using T = tuple<ll,int,int>;
        // min-heap via greater comparator
        auto cmp = greater<T>();
        priority_queue<T, vector<T>, decltype(cmp)> pq(cmp);
        // push (A[i]+B[0], i, 0) for i=0..min(n-1, K-1)
        int lim = min(n, K);
        for(int i = 0; i < lim; i++){
            pq.emplace(A[i] + B[0], i, 0);
        }
        while((int)C.size() < K && !pq.empty()){
            auto [s, i, j] = pq.top();
            pq.pop();
            C.push_back(s);
            if(j + 1 < m){
                pq.emplace(A[i] + B[j+1], i, j+1);
            }
        }
        return C;
    };

    // initial extra-sum list
    vector<ll> L = {0};
    // merge for each type
    for(int j = 1; j <= M; j++){
        if(extra[j].size() <= 1) continue; // only zero -> skip
        L = mergeK(L, extra[j]);
    }
    
    // output K results
    int produced = L.size();
    for(int i = 0; i < produced; i++){
        cout << (base_cost + L[i]) << '\n';
    }
    for(int i = produced; i < K; i++){
        cout << -1 << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5