oj.uz

Submission #550838

# Submission time Handle Problem Language Result Execution time Memory
550838 2022-04-19T10:09:43 Z Soumya1 Watching (JOI13_watching) C++17
100 / 100
 983 ms 16528 KB 
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
void testCase() {
  int n, p, q;
  cin >> n >> p >> q;
  p = min(p, n + 50);
  q = min(q, n + 50);
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a.begin(), a.end());
  auto check = [&](int w) {
    vector<vector<int>> dp(n + 1, vector<int> (p + 1, q + 1));
    vector<int> to(n + 1), to1(n + 1);
    for (int i = 1; i <= n; i++) {
      to[i] = lower_bound(a.begin(), a.end(), a[i] - w + 1) - a.begin() - 1;
      to1[i] = lower_bound(a.begin(), a.end(), a[i] - 2 * w + 1) - a.begin() - 1;
      to[i] = max(0, to[i]);
      to1[i] = max(0, to1[i]);
    }
    dp[0] = vector<int> (p + 1, 0);
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= p; j++) {
        if (j) dp[i][j] = dp[to[i]][j - 1];
        if (dp[to1[i]][j] < q) dp[i][j] = min(dp[i][j], dp[to1[i]][j] + 1);
      }
    }
    return (*min_element(dp[n].begin(), dp[n].end()) <= q);
  };
  int lo = 1, hi = 1e9;
  while (lo < hi) {
    int mid = (lo + hi) >> 1;
    if (check(mid)) hi = mid;
    else lo = mid + 1;
  }
  cout << lo << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

Subtask #1
50.0 / 50.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 212 KB Output is correct
4 Correct 4 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 2 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 740 ms 12292 KB Output is correct
4 Correct 968 ms 16528 KB Output is correct
5 Correct 45 ms 980 KB Output is correct
6 Correct 983 ms 16520 KB Output is correct
7 Correct 12 ms 576 KB Output is correct
8 Correct 65 ms 1408 KB Output is correct
9 Correct 328 ms 6416 KB Output is correct
10 Correct 855 ms 15520 KB Output is correct
11 Correct 47 ms 1124 KB Output is correct
12 Correct 462 ms 8196 KB Output is correct
13 Correct 13 ms 468 KB Output is correct
14 Correct 14 ms 596 KB Output is correct
15 Correct 13 ms 576 KB Output is correct