제출 #1251595

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1251595		dorijanlendvaj	Festival (IOI25_festival)	C++20	100 / 100	109 ms	65588 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using pii=pair<int,int>;
using ll=long long;
using vi=vector<int>;
using vl=vector<ll>;
#define pb push_back
#define all(a) begin(a),end(a)

const int N=300010,MOD=1e9+7,K=32;
const char en='\n';
const ll LLINF=1ll<<60;

bool cmp(pair<pii,int> a,pair<pii,int> b)
{
	return a.x.x*1ll*a.x.y*(b.x.y-1)<b.x.x*1ll*b.x.y*(a.x.y-1);
}

vi max_coupons(int A,vi P,vi T)
{
	int n=P.size();
	vector<pair<pii,int>> coup;
	vector<pii> t1s;
	for (int i=0;i<n;++i) if (T[i]!=1) coup.pb({{P[i],T[i]},i});
	else t1s.pb({P[i],i});
	sort(all(coup),cmp);
	sort(all(t1s));
	int cs=coup.size();
	ll cA=A;
	int cfr=0;
	while (cfr<cs && (cA-coup[cfr].x.x)*coup[cfr].x.y>=cA)
	{
		cA=min(LLINF,(cA-coup[cfr].x.x)*coup[cfr].x.y);
		++cfr;
	}
	vector<vl> dp(cs+1,vl(K+1,-LLINF));
	dp[cfr][0]=cA;
	for (int i=cfr;i<cs;++i)
	{
		for (int j=0;j<=K;++j) dp[i+1][j]=dp[i][j];
		for (int j=0;j<K;++j) dp[i+1][j+1]=max(dp[i+1][j+1],(dp[i][j]-coup[i].x.x)*coup[i].x.y);
	}
	int maxc=0,kak=0;
	for (int uz=0;uz<=K;++uz) if (dp[cs][uz]>=0)
	{
		int kol1=0;
		ll cu=dp[cs][uz];
		for (auto x: t1s) if (cu>=x.x) cu-=x.x,++kol1;
		if (cfr+uz+kol1>maxc) maxc=cfr+uz+kol1,kak=uz;
	}
	vi odg;
	ll kol=dp[cs][kak];
	for (int i=cs-1;i>=cfr;--i) if (dp[i+1][kak]!=dp[i][kak])
	{
		--kak;
		odg.pb(coup[i].y);
	}
	assert(kak==0);
	for (int i=cfr-1;i>=0;--i) odg.pb(coup[i].y);
	reverse(all(odg));
	for (auto x: t1s)
	{
		if (kol>=x.x) kol-=x.x,odg.pb(x.y);
	}
	return odg;
}

• 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