Submission #286738

#	Time	Username	Problem	Language	Result	Execution time	Memory
286738		Ruba_K	Rice Hub (IOI11_ricehub)	C++14	100 / 100	21 ms	3448 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
using namespace std ;


vector<long long>v;
int sz;
long long mx , l , prfsum[1000000];



bool ok(int md){
    long long sum = 0 , mn = 1e18 ;

    for(int i = 0 ; i <= sz - md ; i ++){

        long long mid = (i + md + i) / 2 ;

        long long before = mid - i , after = md + i - 1 - mid ;

        sum = before * v[mid] - prfsum[mid] + prfsum[i] ;
         
        sum +=  (prfsum[md + i] - prfsum [mid + 1] - after * v[mid]);

        mn = min(mn , sum);
        sum = 0 ;


        //B : continue ;

       if(mn <= mx)return true ;
    }
    return false ;

}/*
5 20 6
1 2 10 12 14
3
*/
int besthub(int R, int L, int X[], long long B)
{   mx = B ;l = L , sz = R ;

//    vector<int>v;

    for(int i = 0 ; i < R ; i ++)
        v.push_back(X[i]) , prfsum[i + 1] = prfsum[i] + X[i];

    int l = 0 , r = R , md ;

    while(l < r){
        md = (l + r + 1) / 2 ;

        if(ok(md))l = md ;

        else r = md - 1 ;
    }




    return l ;


}

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