Submission #158345

#	Time	Username	Problem	Language	Result	Execution time	Memory
158345		WLZ	Rice Hub (IOI11_ricehub)	C++14	100 / 100	28 ms	2580 KiB

ricehub

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

int besthub(int R, int L, int X[], long long B) {
  long long T[R + 1];
  T[0] = 0;
  for (int i = 1; i <= R; i++) {
    T[i] = T[i - 1] + X[i - 1];
  }
  int ans = 1;
  for (int s = 0; s < R; s++) {
    int lo = s, hi = R - 1;
    while (lo <= hi) {
      int t = lo + (hi - lo) / 2;
      int p = s + (t - s) / 2;
      long long cost = (p - s) * X[p] - (T[p] - T[s]) + (T[t + 1] - T[p + 1]) - (t - p) * X[p];
      if (cost <= B) {
        ans = max(ans, t - s + 1);
        lo = t + 1;
      } else {
        hi = t - 1;
      }
    }
  }
  return ans;
}

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