Submission #111807

#	Time	Username	Problem	Language	Result	Execution time	Memory
111807		Mercenary	Rice Hub (IOI11_ricehub)	C++14	100 / 100	33 ms	1792 KiB

ricehub

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

using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int a[maxn];
#ifndef LOCAL
#define cerr if(0)cout
#endif // LOCAL
bool Chk(int X[] , int R , ll B , int ask){
    int l = 0 , h = ask - 1;
    ll sum = 0;
    ll suml = 0;
    for(int i = 0 ; i < ask ; ++i){
        sum += X[i];
        if(i <= (l + h) / 2)suml += X[i];
    }
    while(true){
        cerr << ask << " " << sum << " " << suml << endl;
        if((ask % 2) * (ll)X[(l + h) / 2] + sum - 2 * suml <= B)return 1;
        if(h == R - 1)break;
        sum += -X[l] + X[h + 1];
        suml += -X[l] + X[(l + h) / 2 + 1];
        ++l;++h;
    }
    return 0;
}

int besthub(int R, int L, int X[], long long B)
{
    int l = 1;
    int h = R;
    while(l <= h){
        ll mid = l + h >> 1;
        if(Chk(X , R , B , mid))l = mid + 1;
        else h = mid - 1;
    }
//    cerr << Chk(X,R,B,4);
    return h;
}

Compilation message (stderr)

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         ll mid = l + h >> 1;
                  ~~^~~

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