Submission #261544

#	Time	Username	Problem	Language	Result	Execution time	Memory
261544		sandoval	Rice Hub (IOI11_ricehub)	C++11	17 / 100	1092 ms	1536 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+l, a+r+1, p) - a;
    int g = max(0, 1+r-idx);
    int le = max(0, idx-l);
    ll ans = 0;
    for (int i = l; i <= r; ++i) ans += abs(p-a[i]);
    assert(ans == p*1LL*le-sum(ps,l,idx-1)+sum(ps,idx,r)-1LL*g*p);
    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 x[])->long long{
    long long av = sum(ps, l, r)/ll(1+r-l);
    int idx = upper_bound(x+l, x+r+1, av) - x;
    int op1 = idx-1;
    int op2 = idx;
    ll a = numeric_limits<ll>::max();
    ll b = numeric_limits<ll>::max();

    if (op1 >= l && op1 <= r) {
      a = get(l, r, ps, x, x[op1]);
    }

    if (op2 >= l && op2 <= r) {
      b = get(l, r, ps, x, x[op2]);
    }

    return min(a,b);
  };

  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