Submission #418216

#	Time	Username	Problem	Language	Result	Execution time	Memory
418216		dxz05	Rice Hub (IOI11_ricehub)	C++14	100 / 100	23 ms	2540 KiB

ricehub

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

using namespace std;

typedef long long ll;

const int MAXN = 2e5 + 3e2;

ll pref[MAXN];

ll sum(int l, int r){
    ll res = pref[r];
    if (l) res -= pref[l - 1];
    return res;
}

int besthub(int N, int L, int X[], long long B) {
    for (int i = 0; i < N; i++){
        pref[i] = X[i];
        if (i > 0) pref[i] += pref[i - 1];
    }

    int ans = 0;
    for (int i = 0; i < N; i++){
        int l = i, r = N - 1;
        while (l <= r){
            int mid = (l + r) >> 1;

            int ind = (i + mid) / 2;
            int hub = X[ind];

            ll cost = 1ll * hub * (ind - i + 1) - sum(i, ind);
            cost += sum(ind + 1, mid) - 1ll * hub * (mid - ind);

            if (cost <= B){
                ans = max(ans, mid - i + 1);
                l = mid + 1;
            } else r = mid - 1;
        }
    }

    return ans;
}

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