Submission #1235540

#TimeUsernameProblemLanguageResultExecution timeMemory
1235540antromancapWatching (JOI13_watching)C++20
100 / 100
129 ms16132 KiB
#include <bits/stdc++.h> using namespace std; template <class T> bool mini(T &x, const T &y) { return y < x ? x = y, 1 : 0; } template <class T> bool maxi(T &x, const T &y) { return y > x ? x = y, 1 : 0; } const int N = 2005; int n, p, q, dp[N][N], f[N], g[N]; long long a[N]; bool ok(int x) { for (int i = 1; i <= n; i++) { f[i] = upper_bound(a + 1, a + n + 1, a[i] + x - 1) - a; g[i] = upper_bound(a + 1, a + n + 1, a[i] + 2 * x - 1) - a; } f[n + 1] = g[n + 1] = n + 1; for (int i = 0; i <= p; i++) for (int j = 0; j <= q; j++) { dp[i][j] = 1; if (i) maxi(dp[i][j], f[dp[i - 1][j]]); if (j) maxi(dp[i][j], g[dp[i][j - 1]]); } return dp[p][q] > n; } int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> p >> q; for (int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); n = unique(a + 1, a + n + 1) - a - 1; mini(p, n); mini(q, n); int l = 1, r = (a[n] + 1) >> 1; while (l <= r) { int m = (l + r) >> 1; if (ok(m)) r = m - 1; else l = m + 1; } cout << l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...