Submission #1255635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255635		vuviet	Festival (IOI25_festival)	C++20	100 / 100	88 ms	25256 KiB

festival

//#include "festival.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
	int p,t,c;
}a[1000009];
int n;
bool cmp(st a1,st a2){
	if(a1.t==a2.t&&a1.t==1){
		return a1.p<a2.p;
	}
	return a1.p*a1.t*(a2.t-1)<a2.p*a2.t*(a1.t-1);
}
vector<int> dp;
vector<bool> zz[200009];
int l,r;vector<signed> ans;
void dfs(int x,int y){
	if(x<l){
		return;
	}
	if(y==0){
		return;
	}
	if(zz[x][y]){
		dfs(x-1,y-1);
		ans.push_back(a[x].c);
	}else{
		dfs(x-1,y);
	}
}
std::vector<signed> max_coupons(signed aa, std::vector<signed> pp, std::vector<signed> tt) {
	int A;
	A=aa;
	vector<int> P,T;
	P.clear(),T.clear();
	for(int i=0;i<pp.size();i++){
		P.push_back(pp[i]);
		T.push_back(tt[i]);
	}
	for(int i=0;i<(int)P.size();i++){
		a[i]={P[i],T[i],i};
	}
	n=P.size();
	sort(a,a+n,cmp);
	r=n;
	while(r>0&&a[r-1].t==1){
		r--;
	}
	l=r;
	
	ans.clear();
	for(int i=0;i<r;i++){
		if((A-a[i].p)*a[i].t>=A){
			A=(A-a[i].p)*a[i].t;ans.push_back(a[i].c);
			if(A>1e16){
				ans.clear();
				for(int i=0;i<n;i++){
					ans.push_back(a[i].c);
                }
				return ans;
			}
		}else{
			l=i;
			break;
		}
	}
	for(int i=r+1;i<n;i++){
		a[i].p+=a[i-1].p;
	}
	dp.clear();
	dp.push_back(A);
	for(int i=0;i<n;i++){
		zz[i].clear();
	}
	for(int i=l;i<r;i++){
		int g;
		g=dp.size();
		for(int j=0;j<g;j++){
			zz[i].push_back(0);
		}
		if((dp[g-1]-a[i].p)*a[i].t>=0){
			dp.push_back((dp[g-1]-a[i].p)*a[i].t);
			zz[i].push_back(1);
		}
		for(int j=g-2;j>=0;j--){
			if((dp[j]-a[i].p)*a[i].t>dp[j+1]){
				dp[j+1]=(dp[j]-a[i].p)*a[i].t;
				zz[i][j+1]=1;
			}
		}
	}
	int ma,ms;
	ma=ms=0;
	for(int i=0;i<dp.size();i++){
		int p;
		p=0;
		int ll,rr;
		ll=r,rr=n-1;
		while(ll<rr){
			int mid;
			mid=ll+rr+1;
			mid>>=1;
			if(dp[i]>=a[mid].p){
				p=mid-r+1;
				ll=mid;
			}else{
				rr=mid-1;
			}
		}
		if(i+p>ma){
			ma=i+p;
			ms=i;
		}
	}
	dfs(r-1,ms);
	A=dp[ms];
	for(int i=n-1;i>r;i--){
		a[i].p-=a[i-1].p;
	}
	for(int i=r;i<n;i++){
		if(A>=a[i].p){
			A-=a[i].p;
			ans.push_back(a[i].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