Submission #1251617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251617		Zicrus	Festival (IOI25_festival)	C++20	24 / 100	58 ms	10024 KiB

festival

#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(v) v.begin(), v.end()
constexpr ll inf = 1ll << 62ll;
mt19937 mt(34056237);
ll _ = 0;

vector<int> max_coupons(int A, vector<int> price, vector<int> type) {
	ll n = price.size();
	vector<vector<pll>> coups(4+1);
	for (ll i = 0; i < n; i++) {
		coups[type[i]].emplace_back(price[i], i);
	}
	for (ll i = 1; i <= 4; i++) sort(all(coups[i]));

	vector<ll> pref(coups[1].size()+1);
	for (ll i = 1; i <= coups[1].size(); i++) {
		pref[i] = pref[i-1] + coups[1][i-1].first;
	}
	vector<ll> rem(coups[2].size()+1, A);
	for (ll i = 1; i <= coups[2].size(); i++) {
		rem[i] = (rem[i-1] - coups[2][i-1].first) * 2;
		if (rem[i] < 0) {
			rem.resize(i);
			break;
		}
		if(rem[i] > 1e18) {
			rem[i] = 1e18;
		}
	}
	
	ll mx1 = 0, mx2 = 0;
	for (ll t2 = 0; t2 < rem.size(); t2++) {
		ll r = rem[t2];
		ll t1 = (upper_bound(all(pref), r) - pref.begin()) - 1;
		if (t1 + t2 > mx1 + mx2) {
			mx1 = t1;
			mx2 = t2;
		}
	}
	
	vector<int> res;
	for (ll i = 0; i < mx2; i++) {
		res.push_back(coups[2][i].second);
	}
	for (ll i = 0; i < mx1; i++) {
		res.push_back(coups[1][i].second);
	}
	return res;
}

#ifdef TEST
#include "grader.cpp"
#endif

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