# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
737205 | ETheBest3 | 쌀 창고 (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 "ricehub.h"
#include<bits/stdc++.h>
#define lli long long
const lli MAXN=100005;
lli pref[MAXN];
int besthub(int R, int L, int X[], long long B)
{
for(lli i=0; i<R; i++){
if(i==0)pref[i]=X[i];
else pref[i]=pref[i-1]+X[i];
}
lli p1=0, p2=0, p3=0, now=0, sum=0, ans=0;
for(;p2<R; p2++){
now=pref[p2]/(p2+1);
while(p3<p2 and X[p3+1]<=now)p3++;
sum=(pref[p2]-pref[p3])-now*(p2-p3)+now*(p3+1)-pref[p3];
if(sum>B)break;
}
if(sum<=B)return p2;
ans=max(ans, p2);
p2--;
for(p1=0;p1<R; p1++){
for(;p2<R; p2++){
now=(pref[p2]-pref[p1])/(p2-p1);
while(p3<p2 and X[p3+1]<=now)p3++;
sum=(pref[p2]-pref[p3])-now*(p2-p3)+now*(p3-p1)-(pref[p3]-pref[p1]);
if(sum>B)break;
}
ans=max(ans, p2-p1-1);
p2--;
}
return ans;
}