Submission #1253915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1253915		chr34	Festival (IOI25_festival)	C++20	5 / 100	97 ms	12872 KiB

festival

#include <bits/stdc++.h>

using namespace std;

//#define int long long
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
//const int INF = 1e18;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;

vector<int> max_coupons(int a, vector<int> p, vector<int> t) {
    int N = p.size();
    set<pair<int, int>> t1, t2; 

    for (int i = 0; i < N; ++i) {
        if (t[i] == 1) t1.insert({p[i], i});
        else t2.insert({p[i], i});
    }

    vector<int> result;

    while (true) {
        pair<int, int> best = {-1, -1};
        int new_tokens = -1;

        // try best T=2 coupon
        if (!t2.empty()) {
            auto it = t2.begin();
            int cost = it->first, idx = it->second;
            if (a >= cost) {
                int tokens_after = (a - cost) * 2;
                best = {cost, idx};
                new_tokens = tokens_after;
            }
        }

        // Try best T=1 coupon
        if (!t1.empty()) {
            auto it = t1.begin();
            int cost = it->first, idx = it->second;
            if (a >= cost) {
                int tokens_after = a - cost;
                if (new_tokens == -1 || tokens_after > new_tokens) {
                    best = {cost, idx};
                    new_tokens = tokens_after;
                }
            }
        }

        if (best.second == -1) break; 

        int idx = best.second;
        result.push_back(idx);
        if (t[idx] == 1) {
            a = a - p[idx];
            t1.erase({p[idx], idx});
        } else {
            a = (a - p[idx]) * 2;
            t2.erase({p[idx], idx});
        }
    }

    return result;
}

/*int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	//freopen("input.in", "r", stdin);
	//freopen("input.out", "w", stdout);    
	vector<int> ans = max_coupons(13, {4, 500, 8, 14}, {1, 1, 1, 1});
	for(auto x : ans) cout<<x<<endl;	
    return 0;
}*/

• 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