Submission #255130

#	Time	Username	Problem	Language	Result	Execution time	Memory
255130		babo	Rice Hub (IOI11_ricehub)	C++14	100 / 100	31 ms	3328 KiB

ricehub

#include <bits/stdc++.h>

using namespace std;

long long a[100010],nu[100010];
long long n,b;

bool ok(long long x){
	long long i;
	for(i=0;i<n-x+1;i++)
	{
		long long sum=0;
		long long s=i,e=i+x-1,mid=(s+e)/2;
		sum+=a[mid]*(mid-i+1)-(i==0?nu[mid]:(nu[mid]-nu[i-1]));
		sum+=(nu[e]-nu[mid])-a[mid]*(e-mid);
		if(sum<=b) return 1;
	}
	return 0;
}

int besthub(int R,int L,int *X,long long B){
	long long i;
	for(i=0;i<R;i++)
		a[i]=nu[i]=X[i];
	for(i=1;i<R;i++)
		nu[i]+=nu[i-1];
	n=R,b=B;
	long long s=1,e=R;
	while(s<e)
	{
		long long mid=(s+e+1)/2;
		if(ok(mid)) s=mid;
		else e=mid-1;
	}
	return (int)s;
}

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