#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 1000000005
int N, P, Q;
int A[2005];
int ans;
int memo[2005][2005];
int getMinQ(int i, int remP, int v) {
if (i >= N) return 0;
if (memo[i][remP] != -1) return memo[i][remP];
int pNext = upper_bound(A + i, A + N, A[i] + v - 1) - A;
int qNext = upper_bound(A + i, A + N, A[i] + 2 * v - 1) - A;
// if (v == 9) printf("%d: %d, %d\n", i, pNext, qNext);
if (remP == 0) return memo[i][remP] = getMinQ(qNext, remP, v) + 1;
return memo[i][remP] = min(getMinQ(pNext, remP - 1, v), getMinQ(qNext, remP, v) + 1);
}
bool isPossible(int v) {
memset(memo, -1, sizeof memo);
// printf("%d: %d\n", v, getMinQ(0, P, v));
return getMinQ(0, P, v) <= Q;
}
int main() {
scanf("%d%d%d", &N, &P, &Q);
for (int i = 0; i < N; i++)
scanf("%d", &A[i]);
if (P + Q >= N) {
printf("1\n");
return 0;
}
sort(A, A + N);
int lo = 2, hi = INF, mid;
while (lo <= hi) {
mid = (lo + hi) / 2;
if (isPossible(mid)) {
hi = mid - 1;
ans = mid;
} else lo = mid + 1;
}
printf("%d\n", ans);
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:31:7: 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:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i]);
~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
68 ms |
16120 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
68 ms |
16000 KB |
Output is correct |
4 |
Correct |
4 ms |
256 KB |
Output is correct |
5 |
Correct |
4 ms |
384 KB |
Output is correct |
6 |
Correct |
4 ms |
256 KB |
Output is correct |
7 |
Correct |
67 ms |
16000 KB |
Output is correct |
8 |
Correct |
68 ms |
16000 KB |
Output is correct |
9 |
Correct |
68 ms |
16000 KB |
Output is correct |
10 |
Correct |
69 ms |
16120 KB |
Output is correct |
11 |
Correct |
69 ms |
16000 KB |
Output is correct |
12 |
Correct |
69 ms |
16000 KB |
Output is correct |
13 |
Correct |
69 ms |
16120 KB |
Output is correct |
14 |
Correct |
69 ms |
16000 KB |
Output is correct |
15 |
Correct |
67 ms |
16000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
69 ms |
16000 KB |
Output is correct |
2 |
Correct |
5 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
368 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
70 ms |
16000 KB |
Output is correct |
8 |
Correct |
173 ms |
16128 KB |
Output is correct |
9 |
Correct |
460 ms |
16156 KB |
Output is correct |
10 |
Correct |
953 ms |
16348 KB |
Output is correct |
11 |
Correct |
172 ms |
16224 KB |
Output is correct |
12 |
Correct |
816 ms |
16212 KB |
Output is correct |
13 |
Correct |
70 ms |
16000 KB |
Output is correct |
14 |
Correct |
69 ms |
16000 KB |
Output is correct |
15 |
Correct |
70 ms |
16104 KB |
Output is correct |