제출 #528845

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528845		Alex_tz307	Watching (JOI13_watching)	C++17	100 / 100	375 ms	15380 KiB

watching

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