Submission #64678

#	Time	Username	Problem	Language	Result	Execution time	Memory
64678		Abelyan	Rice Hub (IOI11_ricehub)	C++17	0 / 100	1075 ms	612 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>
typedef long long ll;
const int N=100050;
ll sum[N];
ll sm(int l, int r){
  return sum[r]-sum[l-1];
}
int besthub(int n, int sz, int x[], ll b)
{
	int i;
	for(i=1;i<=n;i++) sum[i]=sum[i-1]+x[i];
	int r=n,l=1,mid,ans=1;
	while(r>=l)
	{
		mid=l+r/2;
		bool ok=0;
		for(i=mid;i<=n;i++)
		{
			int L=i-mid+1;
			int R=i;
			int M=L+R/2;
			ll cost=(ll)(M-L+1)*x[M]-sm(L,M);
			cost+=sm(M,R)-(ll)(R-M+1)*x[M];
			if(cost<=b){ ok=1;break;}
		}
		if(ok) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}

• Subtask 1: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32