# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
961050 | raul2008487 | Rice Hub (IOI11_ricehub) | C++17 | 16 ms | 5268 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"
#define ll long long
#define pb push_back
#define eb emplace_back
#define vl vector<ll>
#define fi first
#define se second
#define mpr make_pair
#define lg(x) __lg(x)
#define bpc(x) __builtin_popcount(x)
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
int besthub(int R, int L, int X[], long long B)
{
ll lo = 1, hi = R, mid, best = 1, sum, i, j, n = R, left, right, x;
vl pr(n), sf(n);
pr[0] = X[0];
sf[n - 1] = X[n - 1];
for(i = 1; i < n; i++){
pr[i] = pr[i - 1] + X[i];
}
for(i = n - 2; i >= 0; i--){
sf[i] = sf[i + 1] + X[i];
}
lo = 1, hi = R;
while(lo <= hi){
mid = (lo + hi) >> 1;
if(mid == 1){break;}
bool ok = 0;
for(i = 0; i < n - mid + 1; i++){
if(mid & 1){
left = right = i + (mid / 2);
x = X[left];
}
else{
left = i + (mid / 2) - 1;
right = left + 1;
x = (X[right] + X[left]) / 2;
}
sum = ((left - i + 1) * x) - pr[left];
if(i){sum += pr[i - 1];}
sum += pr[i + mid - 1] - pr[right - 1] - (((i + mid - 1) - right + 1) * x);
ok |= (sum <= B);
}
if(ok){
best = mid;
lo = mid + 1;
}
else{
hi = mid - 1;
}
}
return best;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |