Submission #924834

#	Time	Username	Problem	Language	Result	Execution time	Memory
924834		Lam_lai_cuoc_doi	Rice Hub (IOI11_ricehub)	C++17	100 / 100	25 ms	28564 KiB

ricehub

#include "ricehub.h"

using ll = long long;

bool Check(int num, int R, int L, int X[], long long B) {
  ll *a = new ll[R + 1];
  ll *s = new ll[R + 1];
  for (int i = 1; i <= R; ++i) {
    a[i] = X[i - 1];
    s[i] = s[i - 1] + a[i];
  }

  for (int i = 1; i <= R - num + 1; ++i) {
    int mid = (i + (i + num - 1)) / 2;

    if ((s[i + num - 1] - s[mid]) - (i + num - 1 - mid) * a[mid] + (mid - i + 1) * a[mid] - (s[mid] - s[i - 1]) <= B) {
      return true;
    }
  }

  return false;
}

int besthub(int R, int L, int X[], long long B)
{
  int l = 1, m, h = R;
  while (l <= h) {
    m = (l + h) / 2;
    if (Check(m, R, L, X, B)) {
      l = m + 1;
    } else {
      h = m - 1;
    }
  }

  return h;
}

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