# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1216921 | lizi14 | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
//#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
long long ps[10000];
int besthub(int R, int L, int X[], long long B)
{
//vector<int>v;
for(int i=0; i<R; i++){
//v.push_back(X[i]);
ps[i]=X[i];
if(i>0){
ps[i]+=ps[i-1];
}
}
int l=0,r=R;
int bati=0;
while(l<=r){
int mid=(l+r)/2;
long long ans=1e18;
for(int i=mid/2; i<R-mid/2; i++){
long long ans1=(mid/2)*X[i]-ps[i-1]*(mid/2);
ans1+=(ps[i+mid/2]-ps[i])*(mid/2)-(mid/2)*X[i];
ans=min(ans1,ans);
}
if(ans>B){
r=mid-1;
}
else{
l=mid+1;
bati=mid;
}
}
return bati;
}
int main(){
int R,L,B;
cin>>R>>L;
int X[R];
for(int i=0; i<R; i++){
cin>>X[i];
}
cin>>B;
cout<<besthub(R,L,X,B);
// for(int i=0; i<L; i++){
// cout<<ps[i]<<" ";
// }
}
/*
5 20 6
1 2 10 12 14
*/