Submission #1126058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126058		m_bezrutchka	Rice Hub (IOI11_ricehub)	C++20	100 / 100	16 ms	1984 KiB

ricehub

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

vector<int> x;
int n, l;
long long b;
long long psum[(int)1e5 + 10];

bool ok(int beg, int fin) {
  // printf("ok(%d, %d)\n", beg, fin);
  if (beg == fin) {
    // printf("TRUE\n");
    return true;
  }
  int median = (beg + fin + 1) / 2;
  long long cnt_left = median - beg;
  long long cnt_right = fin - median;
  long long tot = (1LL * x[median]) * (cnt_left - cnt_right);
  // printf("median = %d, cnt_left = %lld, cnt_right = %lld, tot = %lld\n", median, cnt_left, cnt_right, tot);
  // printf("x[%d] = %d\n", median, x[median]);
  tot -= (psum[median - 1] - psum[beg - 1]);
  tot += (psum[fin] - psum[median]);
  // cout << "tot = " << tot << endl;
  return tot <= b;
}

int bin_search(int start) {
  // cout << "bin_search(" << start << ")\n";
  int l = start, r = n;
  while (l < r) {
    int m = (l + r + 1) / 2;
    if (ok(start, m)) {
      l = m;
    } else {
      r = m - 1;
    }
  }
  // cout << "returned " << l << endl;
  return l;
}

int besthub(int R, int L, int X[], long long B)
{
  n = R;
  l = L;
  b = B;
  x.push_back(0);
  for (int i = 0; i < R; i++) {
    x.push_back(X[i]);
    psum[i + 1] = psum[i] + X[i];
  }

  int resp = 0;
  for (int i = 1; i <= R; i++) {
    resp = max(resp, bin_search(i) - i + 1);
  }
  return resp;
}

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