Submission #434157

#	Time	Username	Problem	Language	Result	Execution time	Memory
434157		illyakr	Rice Hub (IOI11_ricehub)	C++14	100 / 100	125 ms	2372 KiB

ricehub

#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
#define ll long long

ll have;
ll n;
ll a[101010];
ll res = 0;
ll pref[101010];
ll gt(ll l, ll r) {
    return pref[r] - pref[l - 1];
}
ll scbp(ll sum, ll id) {
    ll l = 0, r = id + 1;
    while (l + 1 < r) {
        ll mid = (l + r) / 2;
        ll md = (a[id] * (id - mid + 1)) - gt(mid, id);
        if (md + sum > have)l = mid;
        else r = mid;
    }
    return r;
}

int besthub(int R, int L, int X[], long long B) {
    n = R;
    for (ll i = 0; i < R; i++)
        a[i + 1] = X[i];
    have = B;
    for (ll i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i];
    }

    for (ll i = 1; i <= n; i++) {
        ll l = i - 1, r = n + 1;
        while (l + 1 <= r) {
            if (l + 1 == r)break;
            ll mid = (l + r) / 2;
            ll cnt = gt(i, mid) - (a[i] * (mid - i + 1));
            if (cnt > have){r = mid;continue;}
            ll id = scbp(cnt, i);
            res = max(res, mid - id + 1);

            if (id == 1){l = mid;continue;}
            if (abs(a[id - 1] - a[i]) < abs(a[mid] - a[i])){r = mid;continue;}
            l = mid;
        }
    }

    return res;
}

/**
5 20 6
1
2
10
12
14
3
*/

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