Submission #934609

#TimeUsernameProblemLanguageResultExecution timeMemory
934609borisAngelovWatching (JOI13_watching)C++17
100 / 100
495 ms16368 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 2005; const int inf = 1e9; int n, p, q; int a[maxn]; int findPos(int pos, int delta) { int l = 1; int r = pos; while (l <= r) { int mid = (l + r) / 2; if (a[pos] - a[mid] <= delta) { r = mid - 1; } else { l = mid + 1; } } return l; } int prvSmall[maxn]; int prvBig[maxn]; int dp[maxn][maxn]; bool check(int w) { for (int i = 1; i <= n; ++i) { prvSmall[i] = findPos(i, w - 1); prvBig[i] = findPos(i, 2 * w - 1); } for (int pos = 1; pos <= n; ++pos) { for (int currp = 0; currp <= p; ++currp) { dp[pos][currp] = inf; dp[pos][currp] = min(dp[pos][currp], dp[prvBig[pos] - 1][currp] + 1); if (currp >= 1) { dp[pos][currp] = min(dp[pos][currp], dp[pos][currp - 1]); dp[pos][currp] = min(dp[pos][currp], dp[prvSmall[pos] - 1][currp - 1]); } } } for (int i = 0; i <= p; ++i) { if (dp[n][i] <= q) { return true; } } return false; } void fastIO() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int main() { fastIO(); cin >> n >> p >> q; for (int i = 1; i <= n; ++i) { cin >> a[i]; } if (q >= n || p >= n) { cout << 1 << endl; return 0; } sort(a + 1, a + n + 1); int l = 1; int r = 1000000000; while (l <= r) { int mid = (l + r) / 2; if (check(mid) == true) { r = mid - 1; } else { l = mid + 1; } } cout << l << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...