# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1104376 | M_W_13 | Rice Hub (IOI11_ricehub) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++)
ll besthub(ll R, ll L, ll 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;
ll 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;
}