제출 #1254994

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254994		NemanjaSo2005	축제 (IOI25_festival)	C++20	32 / 100	89 ms	8484 KiB

festival

#include "festival.h"
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int maxn=2e5+5;
vector<pair<ll,int>> koji[5];
const ll inf=1e18;
int n;
ll cur,pok[5];
ll perform(ll x,pair<ll,ll> sta){
   return max(min(inf,(x-sta.f)*sta.s),-inf/10);
}
std::vector<int> max_coupons(int A, std::vector<int> P, std::vector<int> T) {
   n=P.size();
   for(int i=1;i<=4;i++)
      pok[i]=1;
   for(int i=1;i<=4;i++)
      koji[i].push_back({0,0});
   for(int i=0;i<n;i++)
      koji[T[i]].push_back({P[i],i});
   for(int i=1;i<=4;i++)
      sort(koji[i].begin(),koji[i].end());
   ll cur=A;
   vector<int> R;
   while(true){
      vector<pair<int,int>> M;
      for(int i=1;i<=4;i++)
         if(pok[i]<koji[i].size() and cur>=koji[i][pok[i]].f){
            M.push_back({koji[i][pok[i]].f,i});
         }
    /*  cout<<M.size()<<endl;
      for(auto x:M)
         cout<<x.f<<" "<<x.s<<" | ";
      cout<<endl;*/
      if(M.size()==0)
         break;
      sort(M.begin(),M.end());
      ll bs=-1e18;
      int radi=-1;
      do{
         ll tmp=cur;
         for(auto x:M)
            tmp=perform(tmp,x);
         if(tmp>bs){
            bs=tmp;
            radi=M[0].second;
         }
      } while(next_permutation(M.begin(),M.end()));
      //cout<<radi<<" "<<pok[radi]<<endl;
      cur=perform(cur,{koji[radi][pok[radi]].f,radi});
      R.push_back(koji[radi][pok[radi]].s);
      pok[radi]++;
   }
   return R;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 12
• Subtask 4: 0 / 15
• Subtask 5: 27 / 27
• Subtask 6: 0 / 16
• Subtask 7: 0 / 18