Submission #133139

#	Time	Username	Problem	Language	Result	Execution time	Memory
133139		zozder	Rice Hub (IOI11_ricehub)	C++14	100 / 100	19 ms	2556 KiB

ricehub

#include "ricehub.h"
#include <iostream>
#include <cstdlib>
#define maxrice 100005
using namespace std;

long long sum[maxrice],l,r,ans;

int besthub(int R, int L, int x[], long long B)
{
	for(int i=0;i<R;i++)sum[i]=x[i];
	for(int i=0;i<R-1;i++)sum[i+1]+=sum[i];
//	for(int i=0;i<R;i++)cout<<x[i]<<"\t";cout<<endl;
//	for(int i=0;i<R;i++)cout<<sum[i]<<"\t";cout<<endl;
	
	l=0;r=0;ans=-1;
	while(l<R&&r<R)
	{
		long long mid=(l+r)/2;//倉之位置
		long long count;
		count = x[mid]*(mid-l) - sum[mid-1] + sum[l-1] + sum[r] - sum[mid] - x[mid]*(r-mid);
		if(count<=B)
		{
			if(r-l+1>ans)ans=r-l+1;
			r++;
		}
		else l++;
	}
	
	return ans;
}

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