oj.uz

Submission #1089015

# Submission time Handle Problem Language Result Execution time Memory
1089015 2024-09-15T18:38:25 Z distiled Watching (JOI13_watching) C++14
100 / 100
 602 ms 31996 KB 
/**
 * Author: distiled
 */
#include<bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#include </Users/distiled/codeStuff/templates/debug.h>
#else
#define dbg(x...)
#endif
#define int int64_t


signed main() {
  ios::sync_with_stdio(false); 
  cin.tie(0);
  int n, p, q;
  cin >> n >> p >> q;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a.begin() + 1, a.end());
  auto ok = [&] (int w) -> bool {
    const int inf = int(1e9);
    vector<vector<int>> dp(n + 1, vector<int>(min(n + 1, p + 1), inf));
    int small = 1, large = 1;
    for (int j = 0; j <= min(n, p); j++) {
      dp[0][j] = 0;
    }
    for (int i = 1; i <= n; i++) {
      while (small <= i && a[i] - a[small] + 1 > w) {
        small += 1;
      }
      while (large <= i && a[i] - a[large] + 1 > 2 * w) {
        large += 1;
      }
      for (int j = 0; j <= min(n, p); j++) {
        if (j == 0) {
          dp[i][j] = min(dp[i][j], dp[large - 1][j] + 1);
        } else {
          dp[i][j] = min({dp[i][j], dp[small - 1][j - 1], dp[large - 1][j] + 1});
        }
      }
    }
    bool ok = false;
    for (int j = 0; j <= min(n, p); j++) {
      ok |= dp[n][j] <= q;
    }
    return ok;
  };

  int l = 0, r = int(1e9), ans = 1e9;
  while (l <= r) {
    int m = (l + r) >> 1;
    if (ok(m)) {
      r = m - 1;
      ans = m;
    } else {
      l = m + 1;
    }
  }
  cout << ans << '\n';
}

Subtask #1
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 379 ms 24148 KB Output is correct
4 Correct 533 ms 31976 KB Output is correct
5 Correct 18 ms 1776 KB Output is correct
6 Correct 602 ms 31996 KB Output is correct
7 Correct 4 ms 604 KB Output is correct
8 Correct 28 ms 2592 KB Output is correct
9 Correct 185 ms 12404 KB Output is correct
10 Correct 527 ms 30420 KB Output is correct
11 Correct 20 ms 1944 KB Output is correct
12 Correct 249 ms 15976 KB Output is correct
13 Correct 6 ms 856 KB Output is correct
14 Correct 6 ms 1096 KB Output is correct
15 Correct 5 ms 812 KB Output is correct