oj.uz

Submission #261547

# Submission time Handle Problem Language Result Execution time Memory
261547 2020-08-11T20:51:58 Z sandoval Rice Hub (IOI11_ricehub) C++11
0 / 100
 5 ms 1128 KB 
#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{
    assert(false);
    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
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 1128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -