Submission #988127

#	Time	Username	Problem	Language	Result	Execution time	Memory
988127		mannshah1211	Rice Hub (IOI11_ricehub)	C++17	100 / 100	16 ms	4460 KiB

ricehub

/**
 *    author: tourist
 *    created:
**/
#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

int besthub(int n, int len, int a[], long long b) {
  vector<long long> p(n + 1);
  for (int i = 0; i < n; i++) {
    p[i + 1] = a[i];
    p[i + 1] += p[i];
  }
  auto rsum = [&](int l, int r) -> int64_t {
    return p[r] - p[l - 1];
  };
  int ans = 1;
  for (int i = 1; i <= n; i++) {
    int low = i + 1, high = n, idx = -1;
    while (low <= high) {
      int mid = (low + high) >> 1, med = (i + mid) >> 1;
      long long cost = int64_t(med - i + 1) * int64_t(a[med]) - rsum(i, med) + rsum(med + 1, mid) - int64_t(mid - med) * int64_t(a[med]);
      if (cost <= b) {
        idx = mid;
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    ans = max(ans, idx - i + 1);
  }
  return ans;
}

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