# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
64674 | 2018-08-05T11:14:11 Z | Abelyan | Rice Hub (IOI11_ricehub) | C++17 | 0 ms | 0 KB |
#include "ricehub.h" #include <bits/stdc++.h> typedef long long ll; const int N=100050; ll sum[N]; ll sm(int l, int r){ return sum[r]-sum[l-1]; } int besthub(int n, int l, int x[], ll b) { int i; for(i=1;i<=n;i++) sum[i]=sum[i-1]+x[i]; int r=n,l=1,mid,ans=1; while(top>=bot) { mid=(l+r)/2; bool ok=0; for(i=mid;i<=n;i++) { int L=i-mid+1; int R=i; int M=(L+R)/2; ll cost=(ll)(M-L+1)*x[M]-sm(L,M); cost+=sm(M,R)-(ll)(R-M+1)*x[M]; if(cost<=b){ ok=1;break;} } if(ok) ans=mid,l=mid+1; else r=mid-1; } return ans; }