Submission #526112

#	Time	Username	Problem	Language	Result	Execution time	Memory
526112		Deepesson	Rice Hub (IOI11_ricehub)	C++17	42 / 100	610 ms	3036 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
typedef std::pair<long long,long long> pli;
typedef std::pair<pli,long long> ppl;
ppl custo(long long P,long long R,int X[],long long B){
    if(P<1)P=1;
    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;long long u=0;
    for(auto&x:vec){
        if(x<=B){
            ++res;
            B-=x;
            continue;
        }else {u=x;break;}
    }
    return {{res,B},(1LL<<60LL)-u};
}
int besthub(int R, int L, int X[], long long B)
{
   int la=1,ra=L-1;
   while(ra-la>1){
        int m = (la+ra)/2;
        ppl alpha = custo(m,R,X,B);
        ppl beta = custo(m+1,R,X,B);
        if(alpha>beta){
            ra=m;
        }else {la=m;}
   }
   ppl ans={{0,0},0};
   for(int i=-5;i!=6;++i){
        ans=std::max(ans,custo(std::min(la+i,L),R,X,B));
   }
   return std::max(ans.first.first,std::max(custo(1,R,X,B).first.first,custo(L,R,X,B).first.first));
}

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