# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1217281 | LeonidCuk | Rice Hub (IOI11_ricehub) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#include "ricehub.h"
using namespace std;
vector<long long int>l,r,v;
long long vrni(long long int l1,long long int m,long long a)
{
long long int s=(m+l1)/2;
return r[m]-r[s]-(m-s)*v[s]+l[s]-l[l1]-(s-l1)*(a-v[s]);
}
int besthub(int n, int x, int v1[], long long k)
{
l.resize(n);
r.resize(n);
v.resize(n);
for(int i=0;i<n;i++)v[i]=v1[i];
long long sum=1;
r[n-1]=v[n-1];
l[0]=x-v[0];
for(int i=1;i<n;i++)
{
l[i]=l[i-1]+x-v[i];
}
for(int i=n-2;i>=0;i--)
{
r[i]=r[i+1]+v[i];
}
for(int i=0;i<n;i++)
{
int l1=i,r1=n-1;
while(l1+1<r1)
{
int m=(l1+r1)/2;
sum=vrni(i,m,x);
if(sum<=k)l1=m;
else r1=m;
}
sum=vrni(i,r1,x);
if(sum<=k)res=max(res,r1-i+1);
res=max(res,l1-i+1);
}
return res;
}
int main()
{
long long int n,m,k;
cin>>n>>m>>k;
int X[n];
for(int i=0;i<n;i++)
{
cin>>X[i];
}
cout<<besthub(n,m,X,k);
}