#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = int(1e3)+5, inf = int(1e9)+5;
int n, p, q, A[maxn], nex[maxn][2];
int DP(int idx, int p)
{
if(idx == n) return 0;
else
{
int res = inf;
if(p) res = min(res, DP(nex[idx][0], p-1));
res = min(res, DP(nex[idx][1], p)+1);
return res;
}
}
bool f(int w)
{
for(int i = 0;i < n;i++)
{
nex[i][0] = int(lower_bound(A, A+n, A[i]+w)-A);
nex[i][1] = int(lower_bound(A, A+n, A[i]+min(inf, 2*w))-A);
}
return (DP(0, p) <= q);
}
int main(void)
{
scanf("%d%d%d", &n, &p, &q);
p = min(p, n), q = min(q, n);
for(int i = 0;i < n;i++) scanf("%d", &A[i]);
sort(A, A+n);
int L = 0, R = inf, ans = inf+5;
while(L <= R)
{
int mid = (L+R)/2;
if(f(mid))
{
ans = min(ans, mid);
R = mid-1;
}
else L = mid+1;
}
printf("%d\n", ans);
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:36:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &p, &q);
^
watching.cpp:38:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0;i < n;i++) scanf("%d", &A[i]);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2032 KB |
Output is correct |
| 2 |
Memory limit exceeded |
39 ms |
262144 KB |
Memory limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
86 ms |
2032 KB |
Execution timed out (wall clock limit exceeded) |
| 2 |
Halted |
0 ms |
0 KB |
- |
