oj.uz

Submission #284027

# Submission time Handle Problem Language Result Execution time Memory
284027 2020-08-26T13:42:02 Z Haunted_Cpp Rice Hub (IOI11_ricehub) C++17
0 / 100
 5 ms 768 KB 
#include "ricehub.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long i64;

int besthub(int R, int L, int X[], i64 B) {
  vector<i64> pre(R), suf(R);
  pre[0] = 0;
  for (int i = 1; i < R; i++) {
    pre[i] = pre[i - 1] + (X[i] - X[i - 1]);
  }
  suf.back() = 0;
  for (int i = R - 2; ~i; i--) {
    suf[i] = suf[i + 1] + (X[i + 1] - X[i]);
  }
  auto range_sum = [&](const vector<i64> &dp, int lo, int hi, bool is_suf) {
    if (!is_suf) return dp[hi] - dp[lo];
    return dp[lo] - dp[hi];
  };
  auto ok = [&](int how_many) {
    for (int i = 0; i <= R - how_many; i++) {
      const int lo = i;
      const int hi = i + how_many - 1;
      const int mid = lo + (hi - lo) / 2;
      i64 dist = 0;
      // Right side
      dist += range_sum(pre, mid, hi, false);
      // Left side
      dist += range_sum(suf, lo, mid, true);
      if (dist <= B) return true;
    }
    return false;
  };
  int lo = 0, hi = R + 7;
  while(lo < hi) {
    const int mid = lo + (hi - lo) / 2;
    if (!ok(mid)) hi = mid;
    else lo = mid + 1;
  }
  return hi - 1;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Incorrect 1 ms 256 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 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

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