Submission #63002

#	Time	Username	Problem	Language	Result	Execution time	Memory
63002		zetapi	Rice Hub (IOI11_ricehub)	C++14	100 / 100	27 ms	2264 KiB

ricehub

#include "ricehub.h"

#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll	long long
#define itr ::iterator 

typedef pair<int,int>  pii;

const int MAX=1e5;

int N,arr[MAX];

int cal(int ind,ll left)
{
	int pre=ind-1,nxt=ind,res=0;
	while(left>=0 and (pre>=0 or nxt<N))
	{
		if(pre<0 or (nxt<N and arr[ind]-arr[pre]>arr[nxt]-arr[ind]))
		{
			if(arr[nxt]-arr[ind]>left)
				break;
			left-=arr[nxt]-arr[ind];
			res++;
			nxt++;
		}
		else
		{
			if(arr[ind]-arr[pre]>left)
				break;
			left-=arr[ind]-arr[pre];
			res++;
			pre--;
		}	
	}
	return res;
}

ll sum[MAX];

ll cal(int L,int R)
{
	ll mid=(L+R)/2,bt=mid-L+1,at=R-mid+1;
	return arr[mid]*bt-(sum[mid]-sum[L-1])+(sum[R]-sum[mid-1])-arr[mid]*at;
}

int besthub(int R, int L, int X[], long long B)
{
	int res=0,start=1;
	N=R;
	for(int A=0;A<N;A++)
		arr[A+1]=X[A];
	for(int A=1;A<=N;A++)
	{
		sum[A]=sum[A-1]+arr[A];
		while(start<A and cal(start,A)>B)
			++start;
		if(cal(start,A)<=B)
			res=max(res,A-start+1);
	}
	//cout<<cal(3,5)<<"\n";
	return res;
}

/*signed main()
{
	ios_base::sync_with_stdio(false);

	int X[]={1,2,10,12,14};
	cout<<besthub(5,20,X,6);	
	return 0;
}*/

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