Submission #1104370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104370		M_W_13	Rice Hub (IOI11_ricehub)	C++17	49 / 100	16 ms	5312 KiB

ricehub

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)

int besthub(int R, int L, int X[], ll B)
{
    ll n = R;
    ll T[n];
    rep(i, n) {
        T[i] = X[i];
    }
    ll ans = 0;
    queue<ll> q;
    ll ile1 = 0;
    ll ile2 = 0;
    ll poz = 0;
    int it = 0;
    ll S = 0;
    while (it < n && S + T[it] <= B) {
        S += T[it];
        q.push(T[it]);
        ile2++;
        it++;
    }
    ans = max(ans, ile1 + ile2);
    rep(i, n) {
        S -= (ile2 * (T[i] - poz));
        S += (ile1 * (T[i] - poz));
        ile1++;
        ile2--;
        poz = T[i];
        // cout << "i = " << i << " poz = " << poz << endl;
        // cout << "ile1 = " << ile1 << " ile2 = " << ile2 << endl;
        // cout << "S = " << S << endl;
        while (S > B) {
            ll x = q.front();
            q.pop();
            S -= (T[i] - x);
            ile1--;
        }
        while (true) {
            // cout << "QQQQQQQ = " << q.front() << '\n';
            if ((it >= n || S + (T[it] - poz) > B) && (it >= n || ((T[it] - poz) >= (poz - q.front())))) {
                break;
            }
            if (S + (T[it] - poz) <= B) {
                S += (T[it] - poz);
                q.push(T[it]);
                ile2++;
            }
            else {
                S -= (poz - q.front());
                q.pop();
                S += (T[it] - poz);
                q.push(T[it]);
                ile2++;
                ile1--;
            }
            it++;
        }
        ans = max(ans, ile1 + ile2);
    }
    return ans;
}

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