Submission #791746

#TimeUsernameProblemLanguageResultExecution timeMemory
791746acatmeowmeowWatching (JOI13_watching)C++11
100 / 100
202 ms11868 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e3; int n, p, q, arr[N + 5], nex[N + 5][2], dp[N + 5][N + 5]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> p >> q; for (int i = 1; i <= n; i++) cin >> arr[i]; if (p + q >= n) { cout << 1 << '\n'; return 0; } 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++) { for (int j = i; j <= n; j++) { if (arr[j] - arr[i] + 1 <= m) nex[i][0] = j; if (arr[j] - arr[i] + 1 <= 2*m) nex[i][1] = j; } } for (int i = 0; i <= p; i++) { for (int j = 0; j <= q; j++) { dp[i][j] = 0; } } for (int i = 0; i <= p; i++) { for (int j = 0; j <= q; j++) { dp[i + 1][j] = max(dp[i + 1][j], nex[min(n, dp[i][j] + 1)][0]); dp[i][j + 1] = max(dp[i][j + 1], nex[min(n, dp[i][j] + 1)][1]); } } if (dp[p][q] == n) 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...