제출 #1254971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254971		NemanjaSo2005	축제 (IOI25_festival)	C++20	24 / 100	59 ms	11176 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];
vector<ll> pref[5];
const ll inf=1e18;
int n;
ll cur;
ll max1(ll x){
   int dg=0,gg=koji[1].size()-1,sred,res;
   while(dg<=gg){
      sred=(dg+gg)/2;
      if(pref[1][sred]<=x){
         res=sred;
         dg=sred+1;
      }
      else
         gg=sred-1;
   }
   return res;
}
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++)
      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());
   for(int i=1;i<=4;i++){
      pref[i].push_back(0);
      for(int j=1;j<koji[i].size();j++)
         pref[i].push_back(pref[i].back()+koji[i][j].f);
   }
   int c1=max1(A),c2=0;
   cur=A;
   for(int i=1;i<koji[2].size();i++){
      cur=(cur-koji[2][i].f)*2;
      cur=min(cur,inf);
      if(cur<0)
         break;
      int m1=max1(cur);
      if(i+m1>c1+c2){
         c1=m1;
         c2=i;
      }
   }
   vector<int> R;
   for(int i=1;i<=c2;i++)
      R.push_back(koji[2][i].second);
   for(int i=1;i<=c1;i++)
      R.push_back(koji[1][i].second);
   return R;
}


void reset(){
   for(int i=1;i<=4;i++){
      koji[i].clear();
      pref[i].clear();
   }
}

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