| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1283020 | lukasuliashvili | 축제 (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "festival.h"
using namespace std;
#define int long long
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
const int INF=1e18,MX=2e14,L=71;
vector<int> max_coupons(int AA,vector<int>P,vector<int>T){
int A=AA;
vector<array<int,3>> x;
int n=P.size();
vector<array<int,2>> y;
rep(i,0,n){
if(T[i]!=1)x.pb({P[i],T[i],i});
else y.pb({P[i],i});
}
sort(x.begin(),x.end(),[&](array<int,3>b,array<int,3>c){
int v1=-b[0]*b[1]*c[1]-c[0]*c[1];
int v2=-c[0]*c[1]*b[1]-b[0]*b[1];
return v1>v2;
});
sort(y.begin(),y.end());
int m=x.size(),k=y.size();
vector<vector<int>> dp(n+1,vector<int>(L,-INF));
vector<vector<int>> par(n+1,vector<int>(L,-1));
int ptr=0;bool bad=false;
for(auto [p,t,_]:x){
if((A-p)*t>=A){
assert(!bad);
A=(A-p)*t;
A=min(A,MX);
ptr++;
}else bad=true;
}
rep(i,0,n+1)dp[i][0]=A;
for(int i=ptr+1;i<=m;i++){
auto [p,t,_]=x[i-1];
rep(j,0,L){
if(dp[i-1][j]>=0){
dp[i][j]=dp[i-1][j];
par[i][j]=0;
}
}
rep(j,0,L-1){
if(dp[i-1][j]>=p){
int val=(dp[i-1][j]-p)*t;
val=min(val,MX);
if(val>dp[i][j+1]){
dp[i][j+1]=val;
par[i][j+1]=1;
}
}
}
}
vector<int> pre(k+1,0);
rep(i,1,k+1)pre[i]=pre[i-1]+y[i-1][0];
int ans=-1,id=-1,ok=-1;
rep(i,0,L){
if(dp[m][i]>=0){
int val=i,l=0,r=k;
while(l!=r){
int mid=(l+r+1)/2;
if(pre[mid]<=dp[m][i])l=mid;
else r=mid-1;
}
val+=l;
if(val>ans)ans=val,id=i,ok=l;
}
}
vector<int> vec;
rep(i,0,ok)vec.pb(y[i][1]);
for(int i=m;i>ptr;i--){
if(par[i][id]==1){
id--;
vec.pb(x[i-1][2]);
}
}
for(int i=ptr-1;i>=0;i--)vec.pb(x[i][2]);
reverse(vec.begin(),vec.end());
return vec;
}