oj.uz

Submission #261583

# Submission time Handle Problem Language Result Execution time Memory
261583 2020-08-11T21:47:38 Z sandoval Rice Hub (IOI11_ricehub) C++11
49 / 100
 241 ms 1664 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 0 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Incorrect 1 ms 256 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 20 ms 376 KB Output is correct
4 Correct 20 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Incorrect 4 ms 384 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 776 KB Output is correct
2 Correct 58 ms 640 KB Output is correct
3 Correct 164 ms 1664 KB Output is correct
4 Correct 230 ms 1656 KB Output is correct
5 Correct 97 ms 1024 KB Output is correct
6 Correct 97 ms 1024 KB Output is correct
7 Correct 153 ms 1664 KB Output is correct
8 Correct 202 ms 1664 KB Output is correct
9 Correct 128 ms 1024 KB Output is correct
10 Correct 129 ms 1024 KB Output is correct
11 Correct 170 ms 1656 KB Output is correct
12 Correct 241 ms 1660 KB Output is correct
13 Correct 151 ms 1024 KB Output is correct
14 Correct 155 ms 1024 KB Output is correct
15 Correct 128 ms 1408 KB Output is correct
16 Correct 183 ms 1408 KB Output is correct
17 Correct 157 ms 1408 KB Output is correct
18 Correct 216 ms 1408 KB Output is correct
19 Correct 162 ms 1536 KB Output is correct
20 Correct 241 ms 1528 KB Output is correct