| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1301212 | wojtaszekliszek | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ll long double
vector<ll>cord(100000);
ll sum(int mid){
if(mid%2==0){
ll mini=LLONG_MAX,sum=0;
int med=mid/2;
for(int i=0;i<mid;i++){
ll comp=cord[i]-(cord[med]+cord[med+1])/2;
sum+=(comp<0?comp*-1:comp);
}
int p=mid-1;
while(cord[p]>0){
mini=min(mini,sum);
sum+=-2*cord[med+1]+cord[p-mid+1]+cord[p+1];
med++;
p++;
//cout<<sum<<' '<<mid<<'\n';
}
return mini;
}
ll mini=LLONG_MAX,sum=0;
int med=(mid-1)/2;
for(int i=0;i<mid;i++){
ll comp=cord[i]-cord[med];
sum+=(comp<0?comp*-1:comp);
}
int p=mid-1;
while(cord[p]>0){
mini=min(mini,sum);
sum+=-cord[med]-cord[med+1]+cord[p-mid+1]+cord[p+1];
med++;
p++;
//cout<<sum<<' '<<mid<<'\n';
}
return mini;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int n,l;
cin>>n>>l;
for(int i=0;i<n;i++){
cin>>cord[i];
}
ll b;
cin>>b;
int p=1,k=n,mid=(n+1)/2;
while(k>p){
if(sum(mid)>b){
k=mid-1;
}
else{
p=mid;
}
mid=(k+p)/2;
}
cout<<mid;
}