Submission #261583

#	Time	Username	Problem	Language	Result	Execution time	Memory
261583		sandoval	Rice Hub (IOI11_ricehub)	C++11	49 / 100	241 ms	1664 KiB

ricehub

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

using namespace std;
using ll = long long;

struct Info{int l, r; ll cost;};

int besthub(int R, int L, int X[], long long B) {
  const int n = R;
  if (n <= 5000) {
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      int curr = 1;
      ll rem = B;
      priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
      if (i-1>=0) pq.push({X[i]-X[i-1], i-1});
      if (1+i<n) pq.push({X[1+i]-X[i], 1+i});
      while (!pq.empty()) {
        auto x = pq.top(); pq.pop();
        if (x.first > rem) break;
        curr++; rem -= x.first;
        int add = 1;
        if (x.second < i) {
          add = -1;
        }

        x.second += add;
        if (x.second >= 0 && x.second < n) {
          pq.push({abs(X[x.second]-X[i]), x.second});
        }
      }

      ans = max(ans, curr);
    }
  }
  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, &n](int A[], int idx, int l, int r, const vector<ll>& ps)->Info{
    int lb = lower_bound(A, A+n, l) - A;
    int ub = upper_bound(A, A+n, r) - A - 1;
    int le = 1+idx-lb;
    int g = ub-idx;
    return Info{lb, ub, 1LL*A[idx]*le-sum(ps, lb, idx) + sum(ps, 1+idx, ub)-1LL*g*A[idx]};
  };

  auto getleft = [&sum, &n](int p, int l, int r, const vector<ll>& ps)->ll{
    const int len = 1+r-l;
    return 1LL*p*len-sum(ps, l, r);
  };

  auto getright = [&sum, &n](int p, int l, int r, const vector<ll>& ps)->ll{
    const int len = 1+r-l;
    return sum(ps, l, r)-1LL*p*len;
  };

  int ans = 1;
  for (int i = 0; i < n; ++i) {
    Info best{-1,-1,-1};
    {
      int low = 0, high = 1e9;
      while (low <= high) {
        int mid = low + ((high-low)/2);
        Info x = get(X, i, X[i]-mid, X[i]+mid, pre);
        if (x.cost <= B) {
          low = 1+mid;
          best = x;
        } else {
          high = mid-1;
        }
      }
    }
    assert(best.l != -1);

    int len = 1+best.r-best.l, op1 = 0, op2 = 0;
    ll rem = B - best.cost;
    assert(rem >= 0);

    {
      int low = 0, high = best.l-1;
      while (low <= high) {
        int mid = (low+high) >> 1;
        if (getleft(X[i], mid, best.l-1, pre) <= rem) {
          high = mid-1;
          op1 = best.l-mid;
        } else {
          low = 1+mid;
        }
      }
    }

    {
      int low = best.r+1, high = n-1;
      while (low <= high) {
        int mid = (low+high) >> 1;
        if (getright(X[i], best.r+1, mid, pre) <= rem) {
          low = 1+mid;
          op2 = mid-best.r;
        } else {
          high = mid-1;
        }
      }
    }

    ans = max(ans, len+max(op1, op2));
  }
  return ans;
}

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