Submission #261527

#	Time	Username	Problem	Language	Result	Execution time	Memory
261527		sandoval	Rice Hub (IOI11_ricehub)	C++11	17 / 100	288 ms	2688 KiB

ricehub

#include "ricehub.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int besthub(int R, int L, int X[], long long B) {
  const int n = R;
  vector<ll> pre(X, X+n);

  for (int i = 1; i < n; ++i) pre[i] += pre[i-1];

  auto sum = [](const vector<ll>& ps, int l, int r)->long long{
    if (l > r) return 0LL;
    ll ans = ps[r];
    if (l > 0) ans -= ps[l-1];
    return ans;
  };

  auto get = [&sum](int l, int r, const vector<ll>& ps, int a[], ll p)->long long{
    int idx = upper_bound(a, a+r+1, p) - a;
    int g = max(0, 1+r-idx);
    int le = max(0, idx-l);
    return p*1LL*le-sum(ps,l,idx-1)+sum(ps,idx,r)-1LL*g*p;
  };

  auto cost = [&get, &sum](int l, int r, const vector<ll>& ps, int a[])->long long{
    long long av = sum(ps, l, r)/ll(1+r-l);
    return min({get(l, r, ps, a, av-1), get(l, r, ps, a, av), get(l, r, ps, a, 1+av)});
  };

  int ans = 1;
  for (int i = 0; i < n; ++i) {
    int low = i, high = n-1, best = -1;
    while (low <= high) {
      int mid = (low+high) >> 1;
      if (cost(i,mid,pre,X) <= B) {
        low = 1+mid;
        best = mid;
      } else {
        high = mid-1;
      }
    }
    assert(best >= i && best < n);
    ans = max(ans, 1+best-i);
  }
  return ans;
}

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