Submission #1283022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283022		lukasuliashvili	Festival (IOI25_festival)	C++20	100 / 100	395 ms	639468 KiB

festival

#include "festival.h"
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
#define all(a) a.begin(),a.end()

const ll INF=1e17;
const int MXN=2e5+7;
const int KK=200;

ll dp[MXN][KK];
pair<int,int> lst[MXN][KK];

pair<ll,ll> ff(pair<ll,ll> x){
  if(x.nd==2ll)return{x.st,1};
  if(x.nd==3ll)return{x.st*3ll,4ll};
  return{x.st*2ll,3ll};
}

bool cmp(pair<pair<ll,ll>,int>a,pair<pair<ll,ll>,int>b){
  auto x=ff(a.st);
  auto y=ff(b.st);
  return(x.st*y.nd)<(y.st*x.nd);
}

ll fn(ll x,pair<ll,ll> p){
  return(x-p.st)*p.nd;
}

vector<int> max_coupons(int A,vector<int>P,vector<int>T){
  int n=P.size();
  vector<pair<pair<ll,ll>,int>> v1;
  vector<pair<ll,int>> v2;
  rep(i,n){
    if(T[i]==1)v2.pb({P[i],i});
    else v1.pb({{P[i],T[i]},i});
  }
  sort(all(v1),cmp);
  sort(all(v2));
  pair<pair<ll,ll>,int> V[n];
  int it=0;
  for(auto p:v1)V[it++]=p;
  for(auto p:v2)V[it++]={{p.st,1ll},p.nd};
  ll val=A;
  vector<int> ans;
  bool use[n];
  rep(i,n)use[i]=false;
  it=0;
  rep(i,n){
    if(val>=INF){
      for(auto x:ans)use[x]=true;
      rep(j,n){
        if(use[j])continue;
        ans.pb(j);
      }
      return ans;
    }
    if(fn(val,V[i].st)>=val){
      val=fn(val,V[i].st);
      ans.pb(V[i].nd);
    }else break;
    it=i+1;
  }
  rep(i,n+1)rep(j,KK)dp[i][j]=-1;
  dp[it][0]=val;
  int n2=v1.size();
  for(int i=it;i<n2;i++){
    dp[i+1][0]=dp[i][0];
    rep(j,KK-1){
      dp[i+1][j+1]=dp[i][j+1];
      lst[i+1][j+1]=lst[i][j+1];
      ll nw=(dp[i][j]-V[i].st.st)*V[i].st.nd;
      if(nw>dp[i+1][j+1]){
        dp[i+1][j+1]=nw;
        lst[i+1][j+1]={i,V[i].nd};
      }
    }
  }
  int s=v2.size();
  ll pre[s+1];
  pre[0]=0;
  rep(i,s)pre[i+1]=pre[i]+v2[i].st;
  int mx=0,kt=s,il2=0,kt2=0;
  rep(il,KK){
    if(dp[n2][il]<0)break;
    while(kt>0&&(pre[kt]>dp[n2][il]))kt--;
    if((kt+il)>mx){
      mx=kt+il;
      il2=il;
      kt2=kt;
    }
  }
  int it1=n2;
  vector<int> tmp;
  while(il2>0){
    tmp.pb(lst[it1][il2].nd);
    it1=lst[it1][il2].st;
    il2--;
  }
  reverse(all(tmp));
  for(auto x:tmp)ans.pb(x);
  rep(i,kt2)ans.pb(v2[i].nd);
  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