Submission #38888

#	Time	Username	Problem	Language	Result	Execution time	Memory
38888		faustaadp	Rice Hub (IOI11_ricehub)	C++14	100 / 100	23 ms	6712 KiB

ricehub

#include "ricehub.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,i,p[101010],b,l,r,c,hs;
bool rct(ll aa,ll bb)
{
	ll hh=0,ce=(aa+bb)/2;
	hh=(p[ce]-p[ce-1])*((ce-1)-aa+1)-(p[ce-1]-p[aa-1])+
	   (p[bb]-p[ce])-(p[ce]-p[ce-1])*(bb-(ce+1)+1);
	//cout<<hh<<" "<<aa<<" "<<bb<<"\n";
	return hh<=b;
}
bool rmt(ll aa)
{
	ll ii;
	for(ii=1;ii+aa-1<=n;ii++)
	{
		if(rct(ii,ii+aa-1))
			return 1;
	}
	return 0;
}
int besthub(int R, int L, int X[], long long B)
{
	n=R;
	for(i=1;i<=n;i++)
	{
		p[i]=p[i-1];
		p[i]+=X[i-1];
	}
	b=B;
	l=0;
	r=R;
	while(l<=r)
	{
		c=(l+r)/2;
		if(rmt(c))
		{
			hs=c;
			l=c+1;
		}
		else
			r=c-1;
	}
  return hs;
}

/*
//#include "ricehub.h"
#include <stdio.h>
#include <stdlib.h>

#define MAX_R  1000000

static int R, L;
static long long B;
static int X[MAX_R];
static int solution;

inline 
void my_assert(int e) {if (!e) abort();}

static void read_input()
{
  int i;
  my_assert(3==scanf("%d %d %lld",&R,&L,&B));
  for(i=0; i<R; i++)
    my_assert(1==scanf("%d",&X[i]));
  my_assert(1==scanf("%d",&solution));
}

int main()
{
  int ans;
  read_input();
  ans = besthub(R,L,X,B);
  if(ans==solution)
    printf("Correct.\n");
  else
    printf("Incorrect.  Returned %d instead of %d.\n",ans,solution);

  return 0;
}
*/

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