Submission #1256129

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256129		WeIlIaN	Festival (IOI25_festival)	C++20	100 / 100	157 ms	162432 KiB

festival

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

#define MOD1 1000000007
#define MOD2 998244353
#define fir first
#define sec second
#define pushf push_front
#define pushb push_back
#define popf pop_front
#define popb pop_back
#define mp make_pair
#define all(a) a.begin(), a.end()

#define FOR1(a) for (ll _ = 0; _ < ll(a); ++_)
#define FOR2(i, a) for (ll i = 0; i < ll(a); ++i)
#define FOR3(i, a, b) for (ll i = a; i < ll(b); ++i)
#define RFOR1(a) for (ll _ = (a)-1; _ >= ll(0); --_)
#define RFOR2(i, a) for (ll i = (a)-1; i >= ll(0); --i)
#define RFOR3(i, a, b) for (ll i = (b)-1; i >= ll(a); --i)
#define overload3(a, b, c, d, ...) d
// Always choose the fourth argument to call. Hence, which function to call is determined by the number of given arguments.
#define REP(...) overload3(__VA_ARGS__, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define RREP(...) overload3(__VA_ARGS__, RFOR3, RFOR2, RFOR1)(__VA_ARGS__)

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
typedef vector<vc> vvc;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<pii> qpii;
typedef queue<pll> qpll;
typedef deque<int> dqi;
typedef deque<ll> dqll;
typedef deque<pii> dqpii;
typedef deque<pll> dqpll;
typedef priority_queue<int> pqi;
typedef priority_queue<ll> pqll;
typedef priority_queue<pii> pqpii;
typedef priority_queue<pll> pqpll;
typedef priority_queue<int, vi, greater<int> > r_pqi;
typedef priority_queue<ll, vll, greater<ll> > r_pqll;
typedef priority_queue<pii, vpii, greater<pii> > r_pqpii;
typedef priority_queue<pll, vpll, greater<pll> > r_pqpll;

const int M = 45;

struct coupon {
	ll p, t;
	int ind;
	coupon(ll _p, ll _t, int _ind) : p(_p), t(_t), ind(_ind) {}
};

bool cmp(const coupon &a, const coupon &b) {
	if(a.t == b.t) {
		return a.p < b.p;
	}
	return a.p*a.t*(b.t-1) < b.p*b.t*(a.t-1);
}

vi max_coupons(int A, vi P, vi T) {
	vector<coupon> coupons, one;
	int n = P.size();
	REP(i, n) {
		if(T[i] == 1) {
			one.emplace_back(P[i], T[i], i);
			continue;
		}
		coupons.emplace_back(P[i], T[i], i);
	}
	sort(all(one), cmp);
	vll pref(one.size() + 1);
	REP(i, 1, one.size()+1) {
		pref[i] = pref[i-1] + one[i-1].p;
	}
	n = coupons.size();
	sort(all(coupons), cmp);
	vi ans;
	ll val = A;
	int pos = n;
	REP(i, n) {
		int p = coupons[i].p, t = coupons[i].t, ind = coupons[i].ind;
		//cerr<<"Processing coupon: " << p << " " << t << " " << ind << ' ' << val <<endl;
		if(val >= p) {
			ll nex = (val - p) * t;
			if(nex >= val) {
				ans.pushb(ind);
				val = nex;
				if(val > 1e16) {
					ans.clear();
					REP(j, n) {
						ans.pushb(coupons[j].ind);
					}
					REP(j, one.size()) {
						ans.pushb(one[j].ind);
					}
					return ans;
				}
			}
			else {
				pos = i;
				break;
			}
		}
	}
	vvll dp(n+1, vll(M, -1)), track(n+1, vll(M, 0));
	REP(i, pos, n+1) {
		dp[i][0] = val;
	}
	REP(i, pos+1, n+1) {
		REP(j, 1, M) {
			ll nex = (dp[i-1][j-1] - coupons[i-1].p) * coupons[i-1].t;
			if(dp[i-1][j-1] >= coupons[i-1].p && nex > dp[i-1][j]) {
				dp[i][j] = nex;
				track[i][j] = 1;
			}
			else {
				dp[i][j] = dp[i-1][j];
			}
		}
	}
	// REP(i, n+1) {
	// 	REP(j, 7) {
	// 		cout<<dp[i][j]<<' ';
	// 	}
	// 	cout<<endl;
	// }
	int best = -1, q = -1;
	REP(j, M) {
		if(dp[n][j] == -1) {
			continue;
		}
		int s = (upper_bound(all(pref), dp[n][j]) - pref.begin()) - 1;
		if(best + q < s + j) {
			best = s;
			q = j;
		}
	}
	vi temp;
	RREP(i, pos+1, n+1) {
		if(q >= 0 && track[i][q] == 1) {
			temp.pushb(coupons[i-1].ind);
			q--;
		}
	}
	reverse(all(temp));
	ans.insert(ans.end(), all(temp));
	REP(i, best) {
		ans.pushb(one[i].ind);
	}
	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