oj.uz

Submission #528845

# Submission time Handle Problem Language Result Execution time Memory
528845 2022-02-21T15:09:12 Z Alex_tz307 Watching (JOI13_watching) C++17
100 / 100
 375 ms 15380 KB 
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

void minSelf(int &x, int y) {
  if (y < x) {
    x = y;
  }
}

void testCase() {
  int n, p, q;
  cin >> n >> p >> q;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  if (p >= n || q >= n) {
    cout << "1\n";
    return;
  }
  auto check = [&](const int &x) -> bool {
    vector<vector<int>> dp(n + 1, vector<int>(p + 1, INF));
    int ptr1 = 1, ptr2 = 1;
    dp[0][0] = 0;
    for (int i = 1; i <= n; ++i) {
      while (a[i] - a[ptr1] >= x) {
        ptr1 += 1;
      }
      while (a[i] - a[ptr2] >= 2 * x) {
        ptr2 += 1;
      }
      for (int j = 0; j <= p; ++j) {
        if (j >= 1) {
          minSelf(dp[i][j], dp[ptr1 - 1][j - 1]);
        }
        minSelf(dp[i][j], dp[ptr2 - 1][j] + 1);
      }
    }
    for (int i = 0; i <= p; ++i) {
      if (dp[n][i] <= q) {
        return true;
      }
    }
    return false;
  };
  sort(a.begin() + 1, a.end());
  int l = 1, r = (a[n] - a[1] + 2) / 2;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      r = mid - 1;
    } else {
      l = mid + 1;
    }
  }
  cout << r + 1 << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int tests = 1;
  for (int tc = 0; tc < tests; ++tc) {
    testCase();
  }
  return 0;
}

Subtask #1
50.0 / 50.0

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

Subtask #2
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 257 ms 12204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 5 ms 460 KB Output is correct
8 Correct 22 ms 1384 KB Output is correct
9 Correct 113 ms 6368 KB Output is correct
10 Correct 375 ms 15380 KB Output is correct
11 Correct 15 ms 1104 KB Output is correct
12 Correct 143 ms 8144 KB Output is correct
13 Correct 4 ms 452 KB Output is correct
14 Correct 4 ms 468 KB Output is correct
15 Correct 5 ms 544 KB Output is correct