Submission #111653

#	Time	Username	Problem	Language	Result	Execution time	Memory
111653		ly20	Rice Hub (IOI11_ricehub)	C++14	100 / 100	25 ms	4344 KiB

ricehub

#include<bits/stdc++.h>
#define debug(args...) //fprintf(stderr,args)
using namespace std;
const int MAXN=112345;
const long long MAXL=1123456789;
long long se[MAXN],sd[MAXN],v[MAXN];
int besthub(int r, int l, int x[], long long b)
{
	for(int i=0;i<r;i++)v[i]=x[i];
	se[0]=v[0];
	debug("esquerda:\nse[%d]=%lld\n",0,se[0]);
	for(int i=1;i<r;i++)
	{
		se[i]=se[i-1]+v[i];
		debug("se[%d]=%lld\n",i,se[i]);
	}
	debug("\n");
	sd[r-1]=l-v[r-1];
	for(int i=r-2;i>=0;i--)sd[i]=sd[i+1]+(l-v[i]);
	debug("direita:\n");
	for(int i=0;i<r;i++)
	{
		debug("sd[%d]=%lld\n",i,sd[i]);
	}
	debug("\n");
	int resp=0;
	int ini=0,fim=0;
	while(fim<r)
	{
		int m=(ini+fim)/2;
		long long cont=0;
		if(m==0)
		{
			cont+=v[fim]-v[ini];
		}
		else if(m!=r-1)
		{
			cont+=se[fim]-se[m-1];
			cont-=(fim-m+1)*v[m];
			cont+=sd[ini]-sd[m+1];
			cont-=(m-ini+1)*(l-v[m]);
		}
		debug("ini=%d fim=%d cost=%lld\n",ini,fim,cont);
		if(cont<=b)
		{
			resp=max(resp,fim-ini+1);
			fim++;
		}
		else ini++;
	}
	return resp;
}

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