#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, p, q, a[N], dp[N][N];
int ok(int w) {
memset(dp, 63, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; ++i) {
auto ip = max(0l, lower_bound(a, a+i, a[i] - w + 1) - a - 1);
auto iq = max(0l, lower_bound(a, a+i, a[i] - 2*w + 1) - a - 1);
for (int j = 0; j <= p; ++j) {
if (j) {
dp[i][j] = min(dp[i][j], dp[ip][j-1]);
}
dp[i][j] = min(dp[i][j], dp[iq][j] + 1);
}
}
for (int j = 0; j <= p; ++j)
if (dp[n][j] <= q) return 1;
return 0;
}
int main() {
scanf("%d%d%d", &n, &p, &q);
p = min(p, n); q = min(q, n);
for (int i = 1; i <= n; ++i) scanf("%d", a+i);
sort(a+1, a+n+1);
int l = -1, r = 1e9+2;
while (r - l > 1) {
auto m = (l+r)/2;
if (ok(m)) r = m;
else l = m;
}
printf("%d", r);
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
27 | scanf("%d%d%d", &n, &p, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
watching.cpp:29:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
29 | for (int i = 1; i <= n; ++i) scanf("%d", a+i);
| ~~~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
16020 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
15956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
61 ms |
15932 KB |
Output is correct |
| 2 |
Incorrect |
56 ms |
15956 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
