Submission #1285316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285316		OmarAlimammadzade	Rice Hub (IOI11_ricehub)	C++20	100 / 100	9 ms	1528 KiB

ricehub

#include "ricehub.h"
#include "bits/stdc++.h"
using namespace std;

#define int long long

int32_t besthub(int32_t n, int32_t x, int32_t a[], int b) {
  int pref[n];
  pref[0] = a[0];
  for (int i = 1; i < n; i++) {
    pref[i] = pref[i - 1] + a[i];
  }
  int lo = 0, hi = n, ans = -1;
  while (lo <= hi) {
    int mid = (lo + hi) / 2;
    int best = 1e18;
    for (int i = 0; i + mid - 1 < n; i++) {
      int med = i + (mid - 1) / 2;
      int cost = 0;
      cost += a[med] * (med - i + 1) - (pref[med] - (i ? pref[i - 1] : 0));
      cost += (pref[i + mid - 1] - pref[med]) - a[med] * (i + mid - 1 - med);
      best = min(best, cost);
    }
    if (best <= b) {
      lo = mid + 1;
      ans = mid;
    } else {
      hi = mid - 1;
    }
  }
  return ans;
}

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