Submission #508831

#	Time	Username	Problem	Language	Result	Execution time	Memory
508831		tabr	Rice Hub (IOI11_ricehub)	C++17	100 / 100	15 ms	1484 KiB

ricehub

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

int besthub(int n, int, int* x, long long b) {
    vector<long long> pref(n + 1);
    for (int i = 0; i < n; i++) {
        pref[i + 1] = pref[i] + x[i];
    }
    int lo = 1;
    int hi = n + 1;
    while (hi - lo > 1) {
        int mid = (hi + lo) / 2;
        int ok = 0;
        for (int i = 0; i + mid <= n; i++) {
            for (int j = max(i, (i + i + mid) / 2 - 1); j <= min(i + mid - 1, (i + i + mid) / 2 + 1); j++) {
                long long c = pref[i + mid] - pref[j] - 1LL * x[j] * (i + mid - j);
                c += 1LL * x[j] * (j - i) - (pref[j] - pref[i]);
                if (c <= b) {
                    ok = 1;
                }
            }
        }
        if (ok) {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    return lo;
}

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