Submission #1248506

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248506		Almonther	Rice Hub (IOI11_ricehub)	C++20	100 / 100	18 ms	2376 KiB

ricehub

#include<bits/stdc++.h>

#define ll long long
#define co cout<<

using namespace std;
// stuff

int besthub(int R,int L,int X[],ll B){
    int mx=0;
    ll pref[R+5]={},suff[R+5]={};
    for(int i=1;i<=R;i++) pref[i]=pref[i-1]+X[i-1];
    for(int i=R-1;i>=0;i--) suff[i]=suff[i+1]+X[i];
    for(int i=0;i<R;i++){
        int len_l=0,len_r=R;
        while(len_l<len_r){
            int mid=(len_l+len_r+1)/2;
            int l=i-mid,r=i+mid;
            if(l<0||r>=R){
                len_r=mid-1;
                continue;
            }
            ll sum=X[i]*(i-l+1)-(pref[i+1]-pref[l]);
            sum+=(suff[i]-suff[r+1])-X[i]*(r-i+1);
            if(sum<=B) len_l=mid;
            else len_r=mid-1;
        }
        mx=max(mx,len_l*2+1);
        if(i<R-1&&X[i+1]-X[i]<=B){
            len_l=1,len_r=R;
            while(len_l<len_r){
                int mid=(len_l+len_r+1)/2;
                int l=i-mid+1,r=i+mid;
                if(l<0||r>=R){
                    len_r=mid-1;
                    continue;
                }
                ll sum=X[i]*(i-l+1)-(pref[i+1]-pref[l]);
                sum+=(suff[i]-suff[r+1])-X[i]*(r-i+1);
                if(sum<=B) len_l=mid;
                else len_r=mid-1;
            }
            mx=max(mx,len_l*2);
        }
    }
    return mx;
}

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