Submission #1213014

#	Time	Username	Problem	Language	Result	Execution time	Memory
1213014		vincentbucourt1	Rice Hub (IOI11_ricehub)	C++20	100 / 100	160 ms	2392 KiB

ricehub

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

int N;
vector<ll> vals;
vector<ll> prefSum;
ll ans = 0;

ll cost (int lb, int ub, int idx) {
  return (prefSum[ub] - prefSum[idx]) - vals[idx]*(ub - idx) + vals[idx]*(idx + 1 - lb) - (prefSum[idx+1] - prefSum[lb]);
}

ll test (int idx, ll len) {
  int lb = lower_bound(vals.begin(), vals.end(), vals[idx] - len) - vals.begin();
  int ub = upper_bound(vals.begin(), vals.end(), vals[idx] + len) - vals.begin();
  return cost(lb, ub, idx);
}

int besthub(int R, int L, int X[], long long B)
{
  N = R;
  vals.resize(N);
  prefSum.assign(N+1, 0);
  for (int i = 0; i < N; i++) {
    vals[i] = X[i];
    prefSum[i+1] = vals[i] + (i > 0 ? prefSum[i] : 0);
  }
  for (int idx = 0; idx < N; idx++) {
    ll lo = 0, hi = L+20;
    while (hi - lo > 1) {
      int mid = lo + (hi - lo) / 2;
      if (test(idx, mid) <= B) {
        lo = mid;
      }
      else {
        hi = mid;
      }
    }

    ll lb = lower_bound(vals.begin(), vals.end(), vals[idx] - lo) - vals.begin();
    ll ub = upper_bound(vals.begin(), vals.end(), vals[idx] + lo) - vals.begin();

    ll numClose = (lb > 0 ? lb - (lower_bound(vals.begin(), vals.end(), vals[lb-1]) - vals.begin()) : 0);
    ll len = (lb > 0 ? vals[idx] - vals[lb-1] : 1);
    if (ub < N-1 && lb > 0 && vals[ub] - vals[idx] < vals[idx] - vals[lb-1]) {
      numClose = 0;
    }
    if (ub < N-1 && (lb == 0 || vals[ub] - vals[idx] <= vals[idx] - vals[lb-1])) {
      len = vals[ub] - vals[idx];
      numClose += (ub < N-1 ? upper_bound(vals.begin(), vals.end(), vals[ub]) - vals.begin() - 1 - ub : 0);
    }

    ll res = ub - lb + min(numClose, (B - cost(lb, ub, idx))/len);
    ans = max(ans, res);
  }
  return ans;
}

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