Submission #362252

#	Time	Username	Problem	Language	Result	Execution time	Memory
362252		WLZ	Rice Hub (IOI11_ricehub)	C++14	58 / 100	18 ms	2560 KiB

ricehub

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

long long r, l, b;
vector<long long> x;

long long query(long long a, long long b) {
  if (a > 0) return x[b] - x[a - 1];
  return x[b];
}

bool check(long long k) {
  for (int i = k - 1; i < r; i++) {
    long long cur = query(i - k / 2 + 1, i) - query(i - k + 1, i - (k + 1) / 2);
    if (cur <= b) return true;
  }
  return false;
}

int besthub(int R, int L, int X[], long long B) {
  r = R, l = L, b = B;
  x = vector<long long>(X, X + r);
  for (int i = 1; i < r; i++) x[i] += x[i - 1];
  long long lo = 2, hi = r;
  while (lo < hi) {
    long long mid = (lo + hi + 1) / 2;
    if (check(mid)) lo = mid;
    else hi = mid - 1;
  }
  return lo;
}

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