Submission #1168714

#TimeUsernameProblemLanguageResultExecution timeMemory
1168714chikien2009Watching (JOI13_watching)C++20
100 / 100
87 ms15944 KiB
#include <bits/stdc++.h> using namespace std; inline void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } int n, p, q, a[2001], f[2001][2001], l = 1, r = 1e9, m, res = 1; inline bool Check(int inp) { for (int i = 1, p1 = 1, p2 = 1; i <= n; ++i) { while (a[p1] + inp - 1 < a[i]) { p1++; } while (a[p2] + 2 * inp - 1 < a[i]) { p2++; } for (int j = 0; j <= p; ++j) { f[i][j] = (j > 0 ? min(f[p1 - 1][j - 1], f[p2 - 1][j] + 1) : f[p2 - 1][j] + 1); } } return (f[n][p] <= q); } int main() { setup(); cin >> n >> p >> q; p = min(p, n); for (int i = 1; i <= n; ++i) { cin >> a[i]; } sort(a + 1, a + 1 + n); while (l <= r) { m = (l + r) >> 1; if (Check(m)) { r = m - 1; res = m; } else { l = m + 1; } } cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...