Submission #284036

#	Time	Username	Problem	Language	Result	Execution time	Memory
284036		Haunted_Cpp	Rice Hub (IOI11_ricehub)	C++17	100 / 100	29 ms	4864 KiB

ricehub

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

typedef long long i64;

int besthub(int R, int L, int X[], i64 B) {
  vector<i64> pre(R), suf(R);
  pre[0] = suf.back() = 0;
  for (int i = 1; i < R; i++) {
    pre[i] = pre[i - 1] + (X[i] - X[i - 1]);
  }
  for (int i = R - 2; ~i; i--) {
    suf[i] = suf[i + 1] + (X[i + 1] - X[i]);
  }
  vector<i64> dp_pre(R), dp_suf(R);
  dp_pre[0] = dp_suf.back() = 0;
  for (int i = 1; i < R; i++) {
    dp_pre[i] = dp_pre[i - 1] + 1LL * i * (X[i] - X[i - 1]);
  }
  for (int i = R - 2; ~i; i--) {
    const int T = R - i - 1;
    dp_suf[i] = dp_suf[i + 1] + 1LL * T * (X[i + 1] - X[i]);
  }
  auto range_sum = [&](const vector<i64> &dp, const vector<i64> &sum, int lo, int hi, bool is_right) -> long long {
    if (is_right) {
      i64 a = dp[lo] - dp[hi];
      i64 b = 1LL * (R - hi - 1) * (sum[lo] - sum[hi]);
      return a - b;
    }
    i64 a = dp[hi] - dp[lo];
    i64 b = 1LL * lo * (sum[hi] - sum[lo]);
    return a - b;
  };
  auto ok = [&](int how_many) {
    for (int i = 0; i <= R - how_many; i++) {
      const int lo = i;
      const int hi = i + how_many - 1;
      const int mid = lo + (hi - lo) / 2;
      i64 dist = 0;
      // Right side
      dist += range_sum(dp_suf, suf, mid, hi, true);
      // Left side
      dist += range_sum(dp_pre, pre, lo, mid, false);
      if (dist <= B) return true;
    }
    return false;
  };
  int lo = 0, hi = R + 7;
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    if (!ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return hi - 1;
}

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