Submission #1254870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1254870		PenguinsAreCute	Festival (IOI25_festival)	C++20	100 / 100	98 ms	60048 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
	long long B = A;
	vector<int> val1;
	vector<long long> pre1 = {0};
	vector<int> rem;
	for(int i=0;i<(int)P.size();i++) {
		if(T[i] == 1)
			val1.push_back(i);
		else
			rem.push_back(i);
	}
	sort(val1.begin(),val1.end(), [&P](int x, int y) {return P[x] < P[y];});
	for(auto i: val1)
		pre1.push_back(pre1.back()+P[i]);
	sort(rem.begin(),rem.end(),[&P,&T](int x, int y) {
		return 1LL * P[x] * T[x] * (T[y] - 1) < 1LL * P[y] * T[y] * (T[x] - 1);
	});
	vector<int> impt;
	vector<int> ans, mid;
	for(auto i: rem) {
		if(1LL * T[i] * (B - P[i]) >= B) {
			B = min(1LL<<60, 1LL * T[i] * (B - P[i]));
			ans.push_back(i);
		} else
			impt.push_back(i);
	}
	int N = impt.size();
	long long dp[N+1][35];
	memset(dp,-1,sizeof(dp));
	dp[0][0] = B;
	for(int i=0;i<N;i++) {
		for(int j=0;j<35;j++)
			dp[i+1][j] = dp[i][j];
		for(int j=0;j<34;j++)
			dp[i+1][j+1] = max(dp[i+1][j+1],1LL * T[impt[i]] * (dp[i][j] - P[impt[i]]));
	}
	pair<int,int> bst = {-1,-1};
	for(int j=0;j<35;j++)
		if(dp[N][j] >= 0) {
			int cnt = upper_bound(pre1.begin(),pre1.end(),dp[N][j]) - pre1.begin() - 1;
			bst = max(bst, {j+cnt, j});
		}
	int j = bst.second;
	int cnt = upper_bound(pre1.begin(),pre1.end(),dp[N][j]) - pre1.begin() - 1;
	for(int i=N;i--;) {
		if(dp[i+1][j] != dp[i][j]) {
			mid.push_back(impt[i]);
			j--;
		}
	}
	reverse(mid.begin(),mid.end());
	for(auto i: mid)
		ans.push_back(i);
	for(int i=0;i<cnt;i++)
		ans.push_back(val1[i]);
	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