# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
919084 | Aiperiii | Rice Hub (IOI11_ricehub) | C++14 | 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>
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
int besthub(int R, int L, long long X[], long long B)
{
vector <long long> sum;long long x=0;
for(int i=0;i<R;i++){
x+=X[i];sum.pb(x);
}
int l=0,r=R+2;
while(l+1<r){
int md=(l+r)/2;
bool ok=0;
for(int i=0;i<R;i++){
long long x=0;
int a=0,b=0;
if(md%2==1){a=md/2;b=md/2;}
else {a=md/2;b=md/2-1;}
if(i>a-1 && i+b<R){
int pos=i-1;
long long d=0;
if(pos>=0)d+=sum[pos];
if(pos-a>=0)d-=sum[pos-a];
x+=X[i]*a-d;
pos=i+b;
d=sum[pos]-sum[i];
x+=d-X[i]*b;
if(x<=B)ok=1;
}
}
if(ok)l=md;
else r=md;
}
return l;
}