Submission #1258261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258261		jamesbamber	Festival (IOI25_festival)	C++20	5 / 100	695 ms	8892 KiB

festival

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

using namespace std;

using ll = long long;

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
	
	int N = P.size();
	
	vector<vector<int>> coupons(4);

	for(int i=0; i<N; i++) {
		coupons[T[i] - 1].push_back(i);
	}

	for(int i=0; i<4; i++) sort(coupons[i].begin(), coupons[i].end(), [&](int a, int b) {
		return P[a] < P[b];
	});

	vector<int> ids(4);

	vector<int> bought;

	long long money = A;

	long long sum = accumulate(P.begin(), P.end(), 0ll);

	while(1) {
		int best = -1;
		long long score = 0;
		for(int i=0; i<4; i++) {
			if(ids[i] >= coupons[i].size() or P[coupons[i][ids[i]]] > money) continue;

			long long p = P[coupons[i][ids[i]]];
			long long t = i + 1;

			cerr << (money - p) * t  << endl;

			if((money - p) * t >= score) {
				score = (money - p) * t;
				best = i;
			}
		}

		cerr << best << endl;

		if(best == -1) break;

		money = score;
		if(money > sum) break;

		bought.push_back(coupons[best][ids[best]]);
		ids[best]++;

	}

	if(money > sum) {
		for(int i=0; i<4; i++) {
			for(int j = ids[i]; j<coupons[i].size(); j++) {
				bought.push_back(coupons[i][j]);
			}
		}
	}

	return bought;
}

• 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