제출 #274728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
274728		bicsi	구경하기 (JOI13_watching)	C++14	100 / 100	197 ms	15276 KiB

watching

#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 / 50
• Subtask 2: 50 / 50