Submission #235011

#	Time	Username	Problem	Language	Result	Execution time	Memory
235011		muhammad_hokimiyon	Rice Hub (IOI11_ricehub)	C++14	100 / 100	31 ms	2304 KiB

ricehub

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

using namespace std;

int besthub(int R, int L, int X[], long long B)
{
    vector < long long > p(R , 0);
    vector < long long > s(R , 0);
    for( int i = 0; i < R; i++ ){
        if( i )p[i] = p[i - 1];
        p[i] += X[i];
    }
    for( int i = R - 1; i >= 0; i-- ){
        if( i < R - 1 )s[i] = s[i + 1];
        s[i] += X[i];
    }
    int ans = 0;
    for( int i = 0; i < R; i++ ){
        int l = 0 , r = i;
        while( l < r ){
            int m = (l + r) / 2;
            int m1 = (m + i) / 2;
            long long x = X[m1];
            if( 1ll * x * (m1 - m + 1) - (p[m1] - (m > 0 ? p[m - 1] : 0)) +
               1ll * (p[i] - p[m1]) - x * (i - m1) > B )l = m + 1;
            else r = m;
        }
        ans = max( ans , i - l + 1 );
    }
    return ans;
}

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