Submission #540819

#	Time	Username	Problem	Language	Result	Execution time	Memory
540819		MohamedFaresNebili	Rice Hub (IOI11_ricehub)	C++14	100 / 100	19 ms	2388 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
 
        using namespace std;
 
        using ll = long long;
        using ii = pair<ll, ll>;
 
        #define ff first
        #define ss second
        #define pb push_back
 
        const int MOD = 1e9 + 7;
 
        int besthub(int R, int L, int X[], long long B) {
            int res = 0; vector<ll> pref(R, 0);
            for(int l = 0; l < R; l++) {
                pref[l] = X[l];
                if(l) pref[l] += pref[l - 1];
            }
            for(int l = 0; l < R; l++) {
                int curr = 1;
                int lo = l, hi = R - 1;
                while(lo <= hi) {
                    int md = (lo + hi) / 2; int d = (md + l) / 2;
                    ll m = X[d];
                    ll calc = m * (d - l + 1) - 2 * pref[d] - m * (md - d) + pref[md];
                    if(l) calc += pref[l - 1];
                    if(calc <= B) lo = md + 1, curr = max(curr, md - l + 1);
                    else hi = md - 1;
                }
                res = max(res, curr);
            }
            return res;
        }

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