# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1276125 | k12_khoi | Rice Hub (IOI11_ricehub) | C++17 | 0 ms | 0 KiB |
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
int n,x,l,r,mid; ll limit;
ll a[N],pre[N];
ll C(int l,int r,int mid)
{
return (pre[r+1]-pre[mid+1])-(r-mid)*a[mid]+a[mid]*(mid-l+1)-(pre[mid+1]-pre[l]);
}
int besthub(int n,int x,ll a[],ll limit)
{
int res=0;
pre[0]=0;
for (int i=1;i<=n;i++)
pre[i]=pre[i-1]+a[i-1];
for (int i=0;i<n;i++)
{
l=(res+1)/2;
r=min(i,n-1-i);
while (l<=r)
{
mid=(l+r)/2;
if (C(i-mid,i+mid,i)<=limit)
{
res=mid*2+1;
l=mid+1;
}
else r=mid-1;
}
l=res/2;
r=min(i,n-2-i);
while (l<=r)
{
mid=(l+r)/2;
if (C(i-mid,i+mid+1,i)<=limit)
{
res=mid*2+2;
l=mid+1;
}
else r=mid-1;
}
}
return res;
}