Submission #211648

#	Time	Username	Problem	Language	Result	Execution time	Memory
211648		mohamedsobhi777	Rice Hub (IOI11_ricehub)	C++14	100 / 100	320 ms	3572 KiB

ricehub

#include <bits/stdc++.h> 
#include "ricehub.h"

using namespace std ;

const int N = 1e5 + 7 ; 

int n ; 
vector<long long> coordinates , prefix; 
long long limit ; 


long long calc(int l , int r){
    if(l>r)return 0ll; 
    return prefix[r] - (l?prefix[l-1]: 0) ;
}

long long sum_abs(int st , int en, long long x){
    int delimeter = upper_bound(coordinates.begin() + st , coordinates.begin() + en +1 , x)  - coordinates.begin() ;
    delimeter-- ; 
    long long ret = 1ll * x * (delimeter - st + 1)  - calc(st , delimeter)+ calc(delimeter+1 , en) - 1ll* (en-delimeter) * x ; 
    return ret ; 
}

bool check(int l , int r){
    int lo = -1 , hi =1e9 ; 
    long long ret = 1e17 ; 
    while(hi - lo > 1){
        int mid = (lo+hi) /2 ; 
        long long get1 = sum_abs(l , r ,mid) ; 
        long long get2 = sum_abs(l , r , mid+1) ; 
        if(get1 >  get2){
            lo = mid ; 
        }
        else {
            hi = mid ; 
        }
    }
    ret = sum_abs(l , r , lo+1) ;
    return ret <= limit ; 
}

int besthub(int R, int L, int X[], long long B)
{
    n = R ; 
    limit = B ; 
    int ans = 1 ; 
    for(int i= 0 ; i<R ; i++){
        if(prefix.size()){
            prefix.push_back(X[i] + prefix.back() ); 
        }
        else {
            prefix.push_back(X[i]);
        }
        coordinates.push_back(X[i]) ; 
    }
    int l = 0 , r = -1 ; 
    while(r< R-1 ){
        r++ ; 
        while( !check(l , r)  )l++ ; 
        ans = max(ans , r-l + 1) ;
    }
    return ans;
}

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