Submission #522624

#	Time	Username	Problem	Language	Result	Execution time	Memory
522624		cig32	Rice Hub (IOI11_ricehub)	C++17	100 / 100	29 ms	3268 KiB

ricehub

#include "ricehub.h"
#define MAXN 100100
#include<algorithm>
using namespace std;
 
long long arr[MAXN];
long long sum[MAXN];
 
int besthub(int R, int L, int X[], long long B)
{
	sort(X,X+R);
	for(int i=0;i<R;i++) arr[i+1]=X[i];
	for(int i=1;i<=R;i++) sum[i]=sum[i-1]+arr[i];
	
	int ans=0;
	for(int i=1;i<=R;i++)
	{
		int lo=0; 
		int hi=min(R-i+1,i);
		while(lo+1!=hi)
		{
			int mi=(lo+hi)/2;
			long long C=sum[i+mi]-sum[i]-sum[i-1]+sum[i-mi-1];
			if(C<=B)
				lo=mi;
			else hi=mi;
		}
		ans=max(ans,2*lo+1);
	}
	for(int i=1;i<=R-1;i++)
	{
		int lo=-1;
		int hi=min(R-i,i);
		while(lo+1!=hi)
		{
			int mi=(lo+hi)/2;
			long long C=arr[i+1] - arr[i] + sum[i+mi+1] - sum[i+1] - sum[i-1] + sum[i-mi-1];
			if(C<=B)
				lo=mi;
			else hi=mi;
		}
		ans=max(ans,2*lo+2);
	}
	return ans;
}

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