Submission #16775

#	Time	Username	Problem	Language	Result	Execution time	Memory
16775		atomzeno	Rice Hub (IOI11_ricehub)	C++98	100 / 100	26 ms	6552 KiB

ricehub

#include "ricehub.h"
#include<algorithm>
#define MX 100004
using namespace std;
long long int x[MX],n,GER[MX];
long long int r=1,BB;
int OK(long long int X){
    long long int i,dd=(X+1)/2,cnt=0,ee=(X/2),s=0;
    for(i=1;i<=(n-dd);i++){
        GER[i]=x[i+dd]-x[i];
    }
    for(i=1;i<=ee;i++){s+=GER[i];}
    if(s<=BB)return 1;
    for(i=ee+1;i<=(n-dd);i++){
        s+=GER[i];
        s-=GER[i-ee];
        if(s<=BB)return 1;
    }
    if(s<=BB)return 0;
}
int besthub(int R, int L, int X[], long long B){
    n=R;
    int s=0,e=n+1,m;
    BB=B;
    int i;
    for(i=1;i<=n;i++){x[i]=X[i-1];}
    sort(x+1,x+1+n);
    for(;;){
        if((s+1)==e)return s;
        m=(s+e)/2;
        if(OK(m)==1){s=m;}
        else{e=m;}
    }
}

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