Submission #687631

#	Time	Username	Problem	Language	Result	Execution time	Memory
687631		beedle	Rice Hub (IOI11_ricehub)	C++17	100 / 100	15 ms	2508 KiB

ricehub

#include "ricehub.h"
#include <iostream>

int besthub(int R, int L, int X[], long long B)
{
  long long cs[R];
  cs[0]=X[0];
  for(int i=1;i<R;i++)
  cs[i]=cs[i-1]+X[i];
  long long lo=1;
  long long hi=R;
  long long best=1;
  while(lo<=hi)
  {
    long long mid=(lo+hi)/2;
    bool possible=false;
    for(int i=0;i<R;i++)
    if(i+mid-1<R)
    {
      long long pivot=i+mid/2;
      long long value=-(cs[pivot-1]-(i==0?0:cs[i-1]))+cs[i+mid-1]-cs[pivot]-X[pivot]*(i+mid-1-pivot)+X[pivot]*(pivot-1-(i-1));
      if(value<=B)
      possible=true;
    } 
    if(possible)
    best=mid, lo=1+mid;
    else
    hi=mid-1;
  }
  return best;
}

// signed main() 
// {
//   int X[]={1,2,10,12,14};
//   std::cout<<besthub(5,20,X,6);
// }

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