Submission #1263626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263626		gelastropod	Festival (IOI25_festival)	C++20	27 / 100	1096 ms	7608 KiB

festival

#include "festival.h"

#include <bits/stdc++.h>
using namespace std;

#define int long long

bool comp(pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
	return (long long)a.second.first * a.second.second * b.second.second + (long long)b.second.first * b.second.second <
		(long long)b.second.first * a.second.second * b.second.second + (long long)a.second.first * a.second.second;
}

std::vector<signed> max_coupons(signed A, std::vector<signed> P, std::vector<signed> T) {
	vector<vector<pair<int, int>>> vals(4, vector<pair<int, int>>());
	for (int i = 0; i < P.size(); i++) {
		vals[T[i] - 1].push_back({ P[i], i });
	}
	vals[0].push_back({ 0, -1 });
	for (int i = 0; i < 4; i++) sort(vals[i].begin(), vals[i].end());
	for (int i = 1; i < vals[0].size(); i++) vals[0][i].first += vals[0][i - 1].first;
	vector<signed> vans;
	int ans = 0;
	for (int i = 0; i <= vals[1].size(); i++) {
		for (int j = 0; j <= vals[2].size(); j++) {
			for (int k = 0; k <= vals[3].size(); k++) {
				vector<pair<int, pair<int, int>>> valss;
				for (int l = 0; l < i; l++) valss.push_back({ vals[1][l].second, {vals[1][l].first, 2} });
				for (int l = 0; l < j; l++) valss.push_back({ vals[2][l].second, {vals[2][l].first, 3} });
				for (int l = 0; l < k; l++) valss.push_back({ vals[3][l].second, {vals[3][l].first, 4} });
				sort(valss.begin(), valss.end(), comp);
				int _A = A;
				int nans = 0, bestI = 0;
				for (int l = 0; l <= valss.size(); l++) {
					auto iter = upper_bound(vals[0].begin(), vals[0].end(), make_pair(_A, (int)INT_MAX));
					iter--;
					if (nans < l + (iter - vals[0].begin())) {
						nans = l + (iter - vals[0].begin());
						bestI = l;
					}
					if (l != valss.size()) _A = valss[l].second.second * (_A - valss[l].second.first);
					if (_A > 1000000000000000 && i + j + k + vals[0].size() > ans) {
						vans.clear();
						ans = i + j + k + vals[0].size();
						for (int m = 0; m < valss.size(); m++) vans.push_back(valss[m].first);
						for (int m = 1; m < vals[0].size(); m++) vans.push_back(vals[0][m].second);
						break;
					}
					if (_A < 0) break;
				}
				if (ans < nans) {
					vans.clear();
					ans = nans;
					for (int l = 0; l < bestI; l++) vans.push_back(valss[l].first);
					for (int l = bestI; l < ans; l++) vans.push_back(vals[0][l + 1 - bestI].second);
				}
			}
		}
	}
	return vans;
}

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