Submission #950892

#	Time	Username	Problem	Language	Result	Execution time	Memory
950892		irmuun	Rice Hub (IOI11_ricehub)	C++17	100 / 100	22 ms	4520 KiB

ricehub

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

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

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