Submission #1255379

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255379		rxlfd314	Festival (IOI25_festival)	C++20	100 / 100	122 ms	123536 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

vt<int> max_coupons(int A, vt<int> P, vt<int> T) {
	const int N = size(P);
	vt<arl2> ones;
	vt<ari3> others;
	FOR(i, 0, N-1) {
		if (T[i] == 1)
			ones.push_back({P[i], i});
		else
			others.push_back({P[i], T[i], i});
	}
	sort(all(ones));
	FOR(i, 1, size(ones)-1)
		ones[i][0] += ones[i-1][0];
	sort(all(others), [&](const ari3 &a, const ari3 &b) {
		return 1ll * a[0] * a[1] * (b[1] - 1) < 1ll * b[0] * b[1] * (a[1] - 1);
	});
	const ll MAX = 2e14;
	const int LOG = 70;
	ll cur = A;
	vt<int> ret;
	int start = -1;
	FOR(ii, 0, size(others)-1) {
		const auto [p, t, i] = others[ii];
		if ((cur - p) * t >= cur) {
			ret.push_back(i);
			cur = min(MAX, (cur - p) * t);
		} else {
			start = ii;
			break;
		}
	}
	if (start >= 0) {
		vt<vt<ll>> dp(size(others) + 1, vt<ll>(LOG + 1, -1));
		dp[start][0] = cur;
		FOR(i, start+1, size(others)) {
			const auto [p, t, _] = others[i-1];
			dp[i][0] = cur;
			FOR(j, 1, LOG) {
				dp[i][j] = max(dp[i-1][j], 1ll * (dp[i-1][j-1] - p) * t); 
			}
		}
		ari2 best = {0, 0};
		FOR(i, 0, LOG) {
			if (dp.back()[i] < 0)
				break;
			const int j = lower_bound(all(ones), arl2{dp.back()[i] + 1, -1}) - ones.begin();
			best = max(best, ari2{i + j, i});
		}
		const int b = best[1];
		int x = b;
		vt<int> sus;
		ROF(i, size(dp)-1, start+1) {
			const auto [p, t, ind] = others[i-1];
			if (dp[i][x] == 1ll * (dp[i-1][x-1] - p) * t) {
				x--;
				sus.push_back(ind);
			}
		}
		reverse(all(sus));
		ret.insert(ret.end(), all(sus));
		const int M = lower_bound(all(ones), arl2{dp.back()[b] + 1, -1}) - ones.begin();
		FOR(i, 0, M-1)
			ret.push_back(ones[i][1]);
	} else {
		const int M = lower_bound(all(ones), arl2{cur + 1, -1}) - ones.begin();
		FOR(i, 0, M-1)
			ret.push_back(ones[i][1]);
	}
	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