Submission #1253149

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253149		anfi	Festival (IOI25_festival)	C++20	5 / 100	77 ms	13484 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long ll;

vector<int> max_coupons(int A, vector<int> P, vector<int> T){
    int cost = A, n = P.size();
    vector<int> ans,use(n, 0);
    vector<pair<ll,int>> mp[5];
    for(int i = 0; i < n; i++){
        mp[T[i]].push_back({P[i],i});
    }
    for(int i = 1; i <= 4; i++) sort(mp[i].begin(), mp[i].end());
    struct item{
        int t, idx;
        ll p;
    };
    struct cmp{
        bool operator()(item const &a, item const &b){
            if(a.t != b.t) return a.t < b.t;
            return a.p > b.p;
        }
    };    
    priority_queue<item, vector<item>, cmp> pq;
    int pr2 = 0, pr3 = 0, pr4 = 0;
    int sz2 = mp[2].size(), sz3 = mp[3].size(), sz4 = mp[4].size();
    
    auto hitung = [&](int t, int &pt, int sz){
        while(pt < sz && mp[t][pt].fi <= cost){
            pq.push({t, mp[t][pt].se, mp[t][pt].fi});
            pt++;
        }
    };

    hitung(4, pr4, sz4);
    hitung(3, pr3, sz3);
    hitung(2, pr2, sz2);
    while(!pq.empty()){
        auto it = pq.top(); pq.pop();
        if(use[it.idx]) continue;
        use[it.idx] = 1;
        cost = (cost-it.p)*it.t;
        ans.push_back(it.idx);
        hitung(4, pr4, sz4);
        hitung(3, pr3, sz3);
        hitung(2, pr2, sz2);
    }

    for(auto &pr : mp[1]){
        if(pr.fi <= cost){
            cost = (cost-pr.fi);
            ans.push_back(pr.se);
        }else break;
    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 0 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18