Submission #562258

#	Time	Username	Problem	Language	Result	Execution time	Memory
562258		four_specks	Rice Hub (IOI11_ricehub)	C++17	100 / 100	25 ms	3332 KiB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

int besthub(int R, int L, int X[], long long B)
{
    vector<long> pref(R + 1, 0), suff(R + 1, 0);
    for (int i = 0; i < R; i++)
        pref[i + 1] = pref[i] + X[i];
    for (int i = R - 1; i >= 0; i--)
        suff[i] = suff[i + 1] - X[i];

    cerr << pref[3] << '\n';

    int res = 0;

    for (int i = 0; i < R; i++)
    {
        int lo = i, hi = R;
        while (lo < hi)
        {
            int mid = (lo + hi + 1) / 2;

            int m = (i + mid) / 2;
            // cerr << i << ' ' << mid << ' ' << m << ' ' << pref[mid] - pref[m] << ' ' << suff[i] - suff[m] << ' ' << (long)(mid - i) * X[m] << '\n';
            if (pref[mid] - pref[m] + suff[i] - suff[m] - (long)(mid - m) * X[m] - (long)(m - i) * -X[m] <= B)
                lo = mid;
            else
                hi = mid - 1;
        }

        res = max(res, lo - i);
    }

    return res;
}

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