Submission #1012682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012682		LucaLucaM	Rice Hub (IOI11_ricehub)	C++17	100 / 100	13 ms	2652 KiB

ricehub

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

typedef long long ll;

int besthub(int n, int l, int a[], long long b) {
  int answer = 0;
  ll sum[n + 1] = {};
  for (int i = 1; i <= n; i++) {
    sum[i] = sum[i - 1] + a[i - 1];
  }
  auto cost = [&](int l, int r) {
    int mid = (l + r) / 2;
    return sum[r] - sum[mid] - (ll) (r - mid) * a[mid - 1] + (ll) (mid - l + 1) * a[mid - 1] - (sum[mid] - sum[l - 1]);
  };
  for (int i = 1, j = 1; i <= n; i++) {
    while (j <= n && cost(i, j) <= b) {
      j++;
    }
    answer = std::max(answer, j - i);
  }
  return answer;
}

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