Submission #1252286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1252286		sofapuden	Festival (IOI25_festival)	C++20	100 / 100	66 ms	8252 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<int> max_coupons(int _a, vector<int> P, vector<int> T) {
	ll A = _a;
	int n = P.size();
	vector<int> od(n);
	iota(od.begin(), od.end(), 0);
	vector<int> ret;
	auto cmp = [&](int x, int y) -> bool { 
		return (-1ll * P[x] * T[x] - P[y]) * T[y] < (-1ll * P[y] * T[y] - P[x]) * T[x]; 
	};
	sort(od.begin(), od.end(), cmp);
	while(od.size() && (A - P[od.back()]) * T[od.back()] >= A) {
		A = min((1ll << 55), (A - P[od.back()]) * T[od.back()]);
		ret.push_back(od.back());
		od.pop_back();
	}
	vector<vector<int>> tk(4);
	while(od.size()) {
		if(T[od.back()] == 1) tk[0].push_back(od.back());
		else if(tk[T[od.back()] - 1].size() < 55) tk[T[od.back()] - 1].push_back(od.back());
		od.pop_back();
	}
	sort(tk[0].begin(), tk[0].end(), [&](auto a, auto b) { return P[a] < P[b]; });
	vector<ll> lef;
	for(auto x : tk[0]) lef.push_back(P[x] + (lef.size() ? lef.back() : 0));
	array<int, 4> bes = {0, 0, 0, 0};
	for(int i = 0; i <= (int)tk[1].size(); ++i){
		for(int j = 0; j <= (int)tk[2].size(); ++j) {
			for(int k = 0; k <= (int)tk[3].size(); ++k) {
				int a = 0, b = 0, c = 0;
				ll cuM = A;
				while(a < i || b < j || c < k) {
					ll mn = -1;
					if(a < i) mn = tk[1][a];
					if(b < j && (mn == -1 || cmp(mn, tk[2][b]))) mn = tk[2][b];
					if(c < k && (mn == -1 || cmp(mn, tk[3][c]))) mn = tk[3][c];
					cuM = (cuM - P[mn]) * T[mn];
					if(T[mn] == 2)a++;
					else if(T[mn] == 3)b++;
					else if(T[mn] == 4)c++;
					if(cuM < 0)break;
				}
				if(cuM < 0) continue;
				bes = max(bes, {a + b + c + (int)(upper_bound(lef.begin(), lef.end(), cuM) - lef.begin()), a, b, c});
			}
		}
	}
	{
		int i = bes[1], j = bes[2], k = bes[3];
		int a = 0, b = 0, c = 0;
		ll cuM = A;
		while(a < i || b < j || c < k) {
			ll mn = -1;
			if(a < i) mn = tk[1][a];
			if(b < j && (mn == -1 || cmp(mn, tk[2][b]))) mn = tk[2][b];
			if(c < k && (mn == -1 || cmp(mn, tk[3][c]))) mn = tk[3][c];
			ret.push_back(mn);
			cuM = (cuM - P[mn]) * T[mn];
			if(T[mn] == 2)a++;
			else if(T[mn] == 3)b++;
			else if(T[mn] == 4)c++;
			if(cuM < 0)break;
		}
		assert(cuM >= 0);
		for(int _i = 0; _i < (int)tk[0].size(); ++_i){ 
			if(cuM >= P[tk[0][_i]]) {
				ret.push_back(tk[0][_i]);
				cuM -= P[tk[0][_i]];
			}
			else break;
		}
	}
	return ret;
}

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