oj.uz

답안 #274728

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
274728 2020-08-19T14:46:16 Z bicsi 구경하기 (JOI13_watching) C++14
100 / 100
 197 ms 15276 KB 
#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, p, q; cin >> n >> p >> q;

  if (p + q >= n) {
    cout << 1 << endl;
    return 0;
  }

  vector<int> a(n);
  for (int i = 0; i < n; ++i) 
    cin >> a[i]; 
  sort(a.begin(), a.end());

  auto ok = [&](int w) -> bool {
    int ps = 0, pl = 0;
    vector<vector<int>> dp(n + 1, vector<int>(p + 1, n + 1));
    fill(dp[0].begin(), dp[0].end(), 0);
    for (int i = 0; i < n; ++i) {
      while (a[ps] <= a[i] - w) ++ps;
      while (a[pl] <= a[i] - 2 * w) ++pl;

      for (int j = 0; j <= p; ++j) {
        if (j > 0) dp[i + 1][j] = min(dp[i + 1][j], dp[ps][j - 1]);
        dp[i + 1][j] = min(dp[i + 1][j], dp[pl][j] + 1);
      }
    }
    return dp[n][p] <= q;
  };
  
  int ans = 0, adv = 1;
  for (int step = 1; step; adv ? step *= 2 : step /= 2) {
    if (ok(ans + step)) adv = 0;
    else ans += step;
  }
  cout << ans + 1 << '\n';

  return 0;
}

Subtask #1
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 1 ms 256 KB Output is correct
9 Correct 1 ms 256 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct

Subtask #2
50.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 384 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 12 ms 512 KB Output is correct
8 Correct 33 ms 1512 KB Output is correct
9 Correct 197 ms 6440 KB Output is correct
10 Correct 52 ms 15276 KB Output is correct
11 Correct 7 ms 1152 KB Output is correct
12 Correct 46 ms 8188 KB Output is correct
13 Correct 9 ms 568 KB Output is correct
14 Correct 13 ms 512 KB Output is correct
15 Correct 14 ms 524 KB Output is correct