Submission #28907

#	Time	Username	Problem	Language	Result	Execution time	Memory
28907		kavun	Rice Hub (IOI11_ricehub)	C++14	100 / 100	26 ms	7488 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll p[200000], bound;
int hub;

bool check(int x, int X[])
{
  int m = (x-1) / 2;
  if((x % 2) && (p[x-1] - p[m] - p[m-1] <= bound))
    return true;
  else if((x % 2 == 0) && (p[x-1] - p[m] - p[m-1] - X[m] <= bound))
    return true;

  for(int i = 1; i <= hub - x; i++)
    {
      int m = i + (x-1)/2;
      if((x % 2) && (p[i+x-1] - p[m] - (p[m-1] - p[i-1]) <= bound))
	  return true;
      else if((x % 2 == 0) && (p[i+x-1] - p[m] - (p[m-1] - p[i-1]) - X[m] <= bound))
	  return true;
    }
  return false;
}

int search(int lo, int hi, int X[])
{
  int m = (lo + hi)/2;
  if(lo == hi)
    return lo;
  if(hi == lo + 1)
    m = hi;
  if(check(m,X))
    return search(m,hi,X);
  else 
    return search(lo,m-1,X);

}

int besthub(int R, int L, int X[], long long B)
{
  bound = B;
  hub = R;
  p[0] = X[0];
  for(int i = 1; i < R; i++)
    p[i] = p[i-1] + X[i];


  return search(1,R,X);
}

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