Submission #757762

#	Time	Username	Problem	Language	Result	Execution time	Memory
757762		taher	Rice Hub (IOI11_ricehub)	C++17	100 / 100	16 ms	2520 KiB

ricehub

#include <bits/stdc++.h>

using namespace std;

int besthub(int R, int L, int X[], long long B) {
  vector<long long> pref(R);
  for (int i = 0; i < R; i++) {
    if (i == 0) pref[i] = (long long) X[i];
    else pref[i] = pref[i - 1] + (long long) X[i];
  }
  int l = 0;
  int best = 0;
  for (int i = 0; i < R; i++) {
    int mid = l + (i - l) / 2;
    int cur = i - mid, here = mid - l;
    long long sum = (pref[i] - pref[mid]) - (long long) X[mid] * cur;
    long long s = 0;
    if (mid > 0) s = (long long) X[mid] * here - (pref[mid - 1] - (l > 0 ? pref[l - 1] : 0));
    if (s + sum <= B) {
      best = max(best, cur + here);
    }
    else {
      l++; i--;
    }
  }
  return best + 1;
}

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