Submission #996405

#	Time	Username	Problem	Language	Result	Execution time	Memory
996405		phoenix	Rice Hub (IOI11_ricehub)	C++17	100 / 100	19 ms	4220 KiB

ricehub

#include<bits/stdc++.h>

using namespace std;


int besthub(int R, int L, int X[], long long B) {
    long long pref[ R ];
    for(int i = 0;i < R;i++) {
        pref[ i ] = X[ i ];
        if(i) pref[ i ] += pref[i - 1];
    }
    auto sum = [&](int l, int r) {
        if(l > r) return 0ll;
        return pref[r] - (l ? pref[l-1] : 0);
    };
    auto func = [&](int l, int r) {
        int m = (l + r) / 2;
        return sum(m + 1, r) - sum(l, m - 1) - X[m] * ((r - l) % 2);
    };
    int res = 0;
    for(int i = 0;i < R;i++) {
        int l = -1, r = i;
        while(r - l > 1) {
            int m = (l + r) / 2;
            if(func(m, i) <= B) r = m;
            else l = m;
        }
        res = max(res, i - l);
    }
    return res;
}

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