제출 #791628

#제출 시각아이디문제언어결과실행 시간메모리
791628acatmeowmeow구경하기 (JOI13_watching)C++11
0 / 100
223 ms404 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e3; int n, p, q, arr[N + 5]; pair<int, int> dp[N + 5][2]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> p >> q; for (int i = 1; i <= n; i++) cin >> arr[i]; sort(arr + 1, arr + n + 1); int l = 1, r = 1e9, ans = 1e9; while (l <= r) { int m = (l + r)/2; for (int i = 1; i <= n; i++) dp[i][0] = dp[i][1] = {-1, -1}; dp[0][0] = dp[0][1] = {q, p}; for (int i = 1; i <= n; i++) { for (int j = 1; j <= i; j++) { for (int k = 0; k < 2; k++) { int prevQ = dp[j - 1][k].first, prevP = dp[j - 1][k].second; if (prevQ && arr[i] - arr[j] + 1 <= 2*m) dp[i][0] = max(dp[i][0], {prevQ - 1, prevP}); if (prevP && arr[i] - arr[j] + 1 <= m) dp[i][1] = max(dp[i][1], {prevQ, prevP - 1}); } } } if (dp[n][0].first != -1 || dp[n][1].first != -1) ans = m, r = m - 1; else l = m + 1; } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...