# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
919084 | 2024-01-31T08:22:05 Z | Aiperiii | Rice Hub (IOI11_ricehub) | C++14 | 0 ms | 0 KB |
#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; }