Submission #99407

#	Time	Username	Problem	Language	Result	Execution time	Memory
99407		naoai	Rice Hub (IOI11_ricehub)	C++14	100 / 100	28 ms	2560 KiB

ricehub

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

using namespace std;

#define fin cin
#define fout cout
//ifstream fin("x.in"); ofstream fout("x.out");

typedef long long i64;
const int nmax = 1e5;

static i64 s[nmax + 1];

bool check (int n, int v[], i64 b, int x) {
    for (int i = x; i <= n; ++ i) {
        int y = (i - x + 1);
        int mij = (y + i) / 2;

        if (b >= s[i] - s[mij] - 1LL * (i - mij) * v[mij] + 1LL * (mij - y + 1) * v[mij] - (s[mij] - s[y - 1])) {
            return 1;
        }
    }
    return 0;
}

int besthub (int n, int l, int v[], i64 b) {
    for (int i = 1; i <= n; ++ i)
        s[i] = s[i - 1] + v[i - 1];

    int n2;
    for (n2 = 1; (n2 << 1) <= n; n2 <<= 1) {
    }

    int ans = 0;
    for (int step = n2; step > 0; step >>= 1) {
        if (ans + step <= n && check(n, v, b, ans + step))
            ans += step;
    }

    return ans;
}

/*int k[5] = {1, 2, 10, 12, 14};

int main() {
    cout << besthub(5, 20, k, 6) << "\n";
    return 0;
}*/

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