Submission #526108

#	Time	Username	Problem	Language	Result	Execution time	Memory
526108		Deepesson	Rice Hub (IOI11_ricehub)	C++17	42 / 100	528 ms	2636 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
typedef std::pair<long long,long long> pli;
pli custo(long long P,long long R,int X[],long long B){
    if(!P)return {0,0};
    std::vector<long long> vec;
    for(int i=0;i!=R;++i){
        long long dist = abs(X[i]-P);
        vec.push_back(dist);
    }
    std::sort(vec.begin(),vec.end());
    int res=0;
    for(auto&x:vec){
        if(x<=B){
            ++res;
            B-=x;
            continue;
        }
    }
    return {res,B};
}
int besthub(int R, int L, int X[], long long B)
{
   long long la=1,ra=L-1;
   while(ra-la>1){
        int m = (la+ra)/2;
        pli alpha = custo(m,R,X,B);
        pli beta = custo(m+1,R,X,B);
        if(alpha>beta){
            ra=m;
        }else {la=m;}
   }
   return std::max(std::max(custo(la+1,R,X,B).first,custo(la,R,X,B).first),std::max(custo(1,R,X,B).first,custo(L,R,X,B).first));
}

• Subtask 1: 17 / 17
• Subtask 2: 25 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32