Submission #1256316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256316		arafatbot144	Festival (IOI25_festival)	C++20	100 / 100	150 ms	172588 KiB

festival

#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
  int n=P.size();
  vector<tuple<ll,int,int,int>>v;
  vector<pair<int,int>>w;
  for(int i=0;i<n;i++){
    if(T[i]!=1)v.push_back({6LL*P[i]*T[i]/(T[i]-1),P[i],T[i],i});
    else w.push_back({P[i],i});
  }
  sort(v.begin(),v.end());
  ll a=A;
  reverse(v.begin(),v.end());
  vector<int>ans1;
  while(!v.empty()&&get<0>(v.back())<=6*a){
    a=(a-get<1>(v.back()))*get<2>(v.back());
    a=min(a,(ll)1e15);
    ans1.push_back(get<3>(v.back()));
    v.pop_back();
  }
  reverse(v.begin(),v.end());
  sort(w.begin(),w.end());
  vector<ll>pref(w.size());
  if(!w.empty())pref[0]=w[0].first;
  for(int i=1;i<w.size();i++){
    pref[i]=pref[i-1]+w[i].first;
  }
  vector<vector<pair<ll,int>>>dp(v.size()+1,vector<pair<ll,int>>(50,{-1,-1}));
  dp[0][0]={a,-1};
  pair<int,int>mx={upper_bound(pref.begin(),pref.end(),a)-pref.begin(),0};
  for(int i=0;i<v.size();i++){
    for(int j=0;j<50;j++){
      dp[i][j].first=min(dp[i][j].first,(ll)1e15);
      dp[i+1][j]=dp[i][j];
      if(j!=0&&dp[i][j-1].first>=get<1>(v[i])){
        dp[i+1][j]=max(dp[i][j],{(dp[i][j-1].first-get<1>(v[i]))*get<2>(v[i]),i});
        mx=max(mx,{j+upper_bound(pref.begin(),pref.end(),dp[i+1][j].first)-pref.begin(),j});
      }
    }
  }
  vector<int>ans;
  for(int i=0;i<mx.first-mx.second;i++){
    ans.push_back(w[i].second);
  }
  int temp=v.size();
  for(;mx.second>0;mx.second--){
    ans.push_back(get<3>(v[dp[temp][mx.second].second]));
    temp=dp[temp][mx.second].second;
  }
  reverse(ans.begin(),ans.end());
  for(int i:ans)ans1.push_back(i);
  return ans1;
}

• 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