oj.uz

Submission #261569

# Submission time Handle Problem Language Result Execution time Memory
261569 2020-08-11T21:35:06 Z sandoval Rice Hub (IOI11_ricehub) C++11
49 / 100
 252 ms 2432 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;
  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;
    {
      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;
        }
      }
    }
    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;
}

Compilation message

ricehub.cpp: In function 'int besthub(int, int, int*, long long int)':
ricehub.cpp:56:16: warning: 'best.Info::r' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int len = 1+best.r-best.l, op1 = 0, op2 = 0;
               ~^~~~~~~
ricehub.cpp:61:20: warning: 'best.Info::l' may be used uninitialized in this function [-Wmaybe-uninitialized]
       int low = 0, high = best.l-1;
                    ^~~~
ricehub.cpp:57:8: warning: 'best.Info::cost' may be used uninitialized in this function [-Wmaybe-uninitialized]
     ll rem = B - best.cost;
        ^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 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 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 0 ms 256 KB Output is correct
11 Incorrect 0 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 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 2 ms 384 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Incorrect 2 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 58 ms 512 KB Output is correct
2 Correct 61 ms 512 KB Output is correct
3 Correct 196 ms 1528 KB Output is correct
4 Correct 249 ms 1536 KB Output is correct
5 Correct 96 ms 896 KB Output is correct
6 Correct 101 ms 896 KB Output is correct
7 Correct 191 ms 1536 KB Output is correct
8 Correct 215 ms 1536 KB Output is correct
9 Correct 125 ms 1152 KB Output is correct
10 Correct 125 ms 1152 KB Output is correct
11 Correct 177 ms 1784 KB Output is correct
12 Correct 252 ms 1792 KB Output is correct
13 Correct 151 ms 1152 KB Output is correct
14 Correct 149 ms 1280 KB Output is correct
15 Correct 131 ms 1664 KB Output is correct
16 Correct 184 ms 1664 KB Output is correct
17 Correct 158 ms 2304 KB Output is correct
18 Correct 221 ms 2304 KB Output is correct
19 Correct 170 ms 2424 KB Output is correct
20 Correct 235 ms 2432 KB Output is correct