Submission #1264132

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264132		am_aadvik	Festival (IOI25_festival)	C++20	5 / 100	1116 ms	2162688 KiB

festival

#include <iostream>
#include<vector>
#include<algorithm>
#define int long long
using namespace std;

vector<int32_t> max_coupons(int32_t a, vector<int32_t> p, vector<int32_t> t) {
	int n = p.size(), v = a;
	vector<pair<int, int32_t>> o[5];
	for (int i = 1; i < 5; ++i) o[i].push_back({ 0, -1 });
	for (int i = 0; i < n; ++i)
		o[t[i]].push_back({ p[i], i });
	for (int i = 1; i < 5; ++i)
		sort(o[i].begin(), o[i].end());
	vector<vector<vector<vector<int>>>> dp(o[1].size(), vector<vector<vector<int>>>
		(o[2].size(), vector<vector<int>>(o[3].size(), vector<int>(o[4].size(), 1e17))));
	vector<vector<vector<vector<int>>>> par(o[1].size(), vector<vector<vector<int>>>
		(o[2].size(), vector<vector<int>>(o[3].size(), vector<int>(o[4].size(), -1))));
	int mx = 0, m1 = 0, m2 = 0, m3 = 0, m4 = 0;
	for(int i = 0; i < o[1].size(); ++i)
		for(int j = 0; j < o[2].size(); ++j)
			for(int k = 0; k < o[3].size(); ++k)
				for (int l = 0; l < o[4].size(); ++l) {
					if (max({ i, j, k, l }) == 0) { dp[i][j][k][l] = v; continue; }
					int res = -1e17, b = 0;
					if (k == 1) {
						k += 0;
					}
					if (i > 0) {
						if (((dp[i - 1][j][k][l] - o[1][i].first) * 1) > res)
							res = max(res, (dp[i - 1][j][k][l] - o[1][i].first) * 1), b = 1;
					}
					if (j > 0) {
						if (((dp[i][j - 1][k][l] - o[2][j].first) * 2) > res)
							res = max(res, (dp[i][j - 1][k][l] - o[2][j].first) * 2), b = 2;
					}
					if (k > 0) {
						if (((dp[i][j][k - 1][l] - o[3][k].first) * 3) > res)
							res = max(res, (dp[i][j][k - 1][l] - o[3][k].first) * 3), b = 3;
					}
					if (l > 0) {
						if (((dp[i][j][k][l - 1] - o[4][l].first) * 4) > res)
							res = (dp[i][j][k][l - 1] - o[4][l].first) * 4, b = 4;
					}
					dp[i][j][k][l] = res;
					par[i][j][k][l] = b;
					if (dp[i][j][k][l] >= 0)
						if ((i + j + k + l) > mx)
							m1 = i, m2 = j, m3 = k,
							mx = (i + j + k + l), m4 = l;
				}
	vector<int32_t> res;
	while (max({ m1, m2, m3, m4 }) > 0) {
		if (par[m1][m2][m3][m4] == 1)
			res.push_back(o[1][m1--].second);
		if (par[m1][m2][m3][m4] == 2)
			res.push_back(o[2][m2--].second);
		if (par[m1][m2][m3][m4] == 3)
			res.push_back(o[3][m3--].second);
		if (par[m1][m2][m3][m4] == 4)
			res.push_back(o[4][m4--].second);
	}
	for (int i = 0; i < res.size() / 2; ++i)
		swap(res[i], res[res.size() - i - 1]);
	return res;
}
/*int32_t main() {
	int n, k; cin >> n >> k;
	vector<int32_t> p(n), t(n);
	for (int i = 0; i < n; ++i)
		cin >> p[i] >> t[i];
	auto res = max_coupons(13, { 4, 500, 8, 14 }, { 1, 3, 3, 4 });
	for(auto x: res) cout << x << " ";

}*/

• 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