Submission #1251237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1251237		ksun48	Festival (IOI25_festival)	C++20	100 / 100	76 ms	8120 KiB

festival

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

template <typename T> void set_min(T& a, const T& b){
	if(b < a) a = b;
}
template <typename T> void set_max(T& a, const T& b){
	if(b > a) a = b;
}

using ll = int64_t;

vector<int> max_coupons(int _A, vector<int> _P, vector<int> T){
	int N = (int)_P.size();
	ll A = _A;
	vector<ll> P(N);
	for(int i = 0; i < N; i++) P[i] = _P[i];
	vector<int> t1;
	vector<int> others;
	for(int i = 0; i < N; i++){
		if(T[i] == 1) t1.push_back(i);
		if(T[i] > 1) others.push_back(i);
	}
	sort(t1.begin(), t1.end(), [&](int i, int j){ return P[i] < P[j]; });
	sort(others.begin(), others.end(), [&](int i, int j){
		return P[i] * (T[i]) * 6 / (T[i] - 1) < P[j] * (T[j]) * 6 / (T[j] - 1);
	});
	vector<int> ans;
	ll BUY_ALL = 0;
	for(ll x : P) BUY_ALL += x;
	{
		int idx = 0;
		while(idx < (int)others.size()){
			int i = others[idx];
			if(A <= (A - P[i]) * T[i]){
				A = (A - P[i]) * T[i];
				ans.push_back(i);
				idx++;
			} else break;
			if(A >= BUY_ALL){
				ans = others;
				ans.insert(ans.end(), t1.begin(), t1.end());
				return ans;
			}
		}
		others.erase(others.begin(), others.begin() + idx);
	}
	{
		int B = 64;
		vector<int> found_freq(5);
		vector<int> new_others;
		for(int x : others){
			if(found_freq[T[x]] >= B) continue;
			found_freq[T[x]]++;
			new_others.push_back(x);
		}
		others = new_others;
	}

	int L = (int)others.size();
	vector<vector<ll> > dp(L+1, vector<ll>(L+1, -1));
	dp[0][0] = A;
	for(int l = 0; l < L; l++){
		int i = others[l];
		dp[l+1] = dp[l];
		for(int c = 0; c+1 <= L; c++){
			if(dp[l][c] >= P[i]){
				set_max(dp[l+1][c+1], (dp[l][c] - P[i]) * T[i]);
			}
		}
	}
	vector<ll> t1_sums(t1.size() + 1);
	for(int idx = 0; idx < (int)t1.size(); idx++){
		t1_sums[idx+1] = t1_sums[idx] + P[t1[idx]];
	}
	int best_cnt = -1;
	int best_c = -1;
	for(int c = 0; c <= L; c++){
		if(dp[L][c] >= 0){
			int cnt = c + (lower_bound(t1_sums.begin(), t1_sums.end(), dp[L][c]+1) - t1_sums.begin() - 1);
			if(cnt >= best_cnt){
				best_cnt = cnt;
				best_c = c;
			}
		}
	}
	vector<int> used;
	int cur_c = best_c;
	for(int l = L-1; l >= 0; l--){
		if(dp[l+1][cur_c] == dp[l][cur_c]) continue;
		assert(cur_c > 0);
		int i = others[l];
		used.push_back(i);
		cur_c--;
	}
	reverse(used.begin(), used.end());
	ans.insert(ans.end(), used.begin(), used.end());
	ans.insert(ans.end(), t1.begin(), t1.begin() + (best_cnt - best_c));
	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