Submission #1256678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256678		Jasonwei	Festival (IOI25_festival)	C++17	100 / 100	494 ms	252840 KiB

festival

/*
-A2 --indent=tab=4 --indent-classes --indent-switches --indent-namespaces --indent-preprocessor -xg -p -xd -H -xj -xe

read all problems
do first-eye problems
read rev order

uhhh dont fail impl
*/
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define re(a, b, c, d) for (int a = b; a <= c; a += d)
#define de(a, b, c, d) for (int a = b; a >= c; a -= d)
#define ms(a, b) memset(a, b, sizeof (a))
#define imax INT_MAX
#define imin INT_MIN
#define wh(a) while (a --)
#define PII pair <int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
template <typename T> bool chkmin (T &a, T b) {
	return (b < a) ? a = b, 1 : 0;
}
template <typename T> bool chkmax (T &a, T b) {
	return (b > a) ? a = b, 1 : 0;
}
using namespace std;
#include "festival.h"
const int N = 2e5 + 5;
vector<int> max_coupons (int A, vector<int> P, vector<int> T) {
	int n = P.size();
	vector<int> ids (n);
	iota (ids.begin(), ids.end(), 0);
	sort (ids.begin(), ids.end(), [&] (int a, int b) {
		if ((ll)P[a] * T[a] * (T[b] - 1) != (ll)P[b] * T[b] * (T[a] - 1))
			return (ll)P[a] * T[a] * (T[b] - 1) < (ll)P[b] * T[b] * (T[a] - 1);
		return P[a] < P[b];
	});
	vector <map <int, pair<ll, bool> > > f (n + 1); 
	f[0][0] = {A, 0};
	re (i, 0, n - 1, 1) {
		int p = P[ids[i]], t = T[ids[i]];
		for (auto [c, val] : f[i]) {
			auto [x, y] = val;
			auto& v = f[i + 1][c];
			chkmax (v, {x, 0});
			if (p <= x) {
				auto& u = f[i + 1][c + 1];
				chkmax (u, {min ((ll)1e15, (x - p) * t), 1});
			}
		}
		while (f[i + 1].size() >= 20) f[i + 1].erase (f[i + 1].begin());
	}
	int j = f[n].rbegin() -> F;
	vector<int> ans;
	de (i, n - 1, 0, 1){
		if (!f[i + 1][j].S) continue;
		ans.pb (ids[i]);
		j--;
	}
	reverse (ans.begin(), ans.end());
	return ans;
}

• 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