Submission #284027

#	Time	Username	Problem	Language	Result	Execution time	Memory
284027		Haunted_Cpp	Rice Hub (IOI11_ricehub)	C++17	0 / 100	5 ms	768 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] = 0;
  for (int i = 1; i < R; i++) {
    pre[i] = pre[i - 1] + (X[i] - X[i - 1]);
  }
  suf.back() = 0;
  for (int i = R - 2; ~i; i--) {
    suf[i] = suf[i + 1] + (X[i + 1] - X[i]);
  }
  auto range_sum = [&](const vector<i64> &dp, int lo, int hi, bool is_suf) {
    if (!is_suf) return dp[hi] - dp[lo];
    return dp[lo] - dp[hi];
  };
  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(pre, mid, hi, false);
      // Left side
      dist += range_sum(suf, lo, mid, true);
      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: 0 / 17
• Subtask 2: 0 / 25
• Subtask 3: 0 / 26
• Subtask 4: 0 / 32