Submission #684359

#	Time	Username	Problem	Language	Result	Execution time	Memory
684359		kusssso	Rice Hub (IOI11_ricehub)	C++17	100 / 100	70 ms	2380 KiB

ricehub

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 5;

ll f[N];

bool check (ll x, ll b, int l, int r, vector<ll> &a) {
    int j = upper_bound(a.begin(), a.end(), x) - a.begin();
    j = min(j, r - 1);
    ll sum = x * (j - l + 1) - (f[j] - f[l - 1]) + (f[r] - f[j]) - x * (r - j);
    return (sum <= b);
}

bool ok (int k, ll b, int n, vector<ll> &a) {
    for (int i = k; i <= n; i++) {
        // ll med = (f[i] - f[i - k]) / k;
        ll med = a[i - k + (k + 1) / 2];
        if (check(med, b, i - k + 1, i, a)) {
            return true;
        }
        if (check(med + 1, b, i - k + 1, i, a)) {
            return true;
        }
        if (check(med - 1, b, i - k + 1, i, a)) {
            return true;
        }
    }
    return false;
}

// int besthub (int r, int l, vector<int> x, ll b) {
int besthub (int r, int l, int x[], ll b) {
    vector<ll> a;
    for (int i = 0; i < r; i++) {
        f[i + 1] = f[i] + x[i];
        a.push_back(x[i]);
    }
    int ans = 0;
    int lo = 0, hi = r;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (ok(mid, b, r, a)) {
            ans = mid;
            lo = mid + 1;
        }
        else {
            hi = mid - 1;
        }
    }
    return ans;
}

// signed main() {
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
//     
    // cout << besthub(5, 20, {1, 2, 10, 12, 14}, 6);
//     
    // return 0;
// }

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