Submission #1104385

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

ricehub

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

using namespace std;
typedef long long ll;
#define rep(i, n) for (ll 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 p = 0;
    ll k = n + 1;
    ll ans = k;
    while (p < k) {
        ll sr = (p + k)/2;
        int i1 = 0;
        int i2 = sr/2;
        ll ilelewa = i2 + 1;
        ll ileprawa = sr - ilelewa;
        ll S = 0;
        bool czy = false;
        rep(i, sr) {
            S += (abs(T[i] - T[i2]));
        }
        if (S <= B) {
            czy = true;
        }
        i1++;
        while (i1 + sr - 1 < n) {
            S -= abs(T[i1 - 1] - T[i2]);
            S += abs(T[i1 + sr - 1] - T[i2]);
            ilelewa--;
            ileprawa++;
            ll poz = T[i2];
            i2++;
            S += (ilelewa * (T[i2] - poz));
            S -= (ileprawa * (T[i2] - poz));
            ilelewa++;
            ileprawa--;
            if (S <= B) {
                czy = true;
            }
            i1++;
        }
        if (czy) {
            ans = sr;
            p = sr + 1;
        }
        else {
            k = sr;
        }
    }   
    return ans;
}

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