oj.uz

Submission #787564

# Submission time Handle Problem Language Result Execution time Memory
787564 2023-07-19T09:45:17 Z bane Rice Hub (IOI11_ricehub) C++17
0 / 100
 6 ms 724 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

int besthub(int R, int L, int x[], long long B)
{

  vector<long long>X(R+1);
  X[0] = -(long long)1e18;
  for (int i = 1; i <= R; i++){
    X[i] = x[i - 1];
  }
  int l = 1, r = R;
  long long pf[R+1];
  pf[0] = 0;
  for (int i = 1; i<=R; i++){
    pf[i] = pf[i - 1] + X[i];
  }

  function<bool(int)>check = [&](int mid){
    int r = 0;
    int l = 1;
    while(r + 1 <= R){
      ++r;
      while(r - l + 1 > mid){
        ++l;
      }

      long long avg = pf[r] - pf[l - 1];
      if (r - l + 1 == mid){
        int itt = upper_bound(X.begin(), X.end(), avg) - X.begin();
        for (auto it : {itt,itt-1}){
          if (it < l || it > r)continue;
          long long sum = 0;
          if (it != l){
            sum += (it - l) * X[it] - (pf[it-1] - pf[l-1]);
          }
          if (it != r){
            sum += -(r - it) * X[it] + (pf[r] - pf[it]);
          }
          if (sum <= B)return true;
        }
      }
    }

    return false;
  };
  while(l<=r){
    int mid = (l+r) / 2;
    if (check(mid)){
      l = mid + 1;
    }else{
      r = mid - 1;
    }
  }
  return l - 1;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 724 KB Output isn't correct
2 Halted 0 ms 0 KB -