#include <cstdio>
#include <cstring>
#include <algorithm>
template<typename T> bool ckmax(T& a, T b){return a<b?a=b,1:0;}
template<typename T> bool ckmin(T& a, T b){return a>b?a=b,1:0;}
const int MN = 2e3+10;
int N, P, Q, dp[MN][MN], a[MN], nex[MN][2];
bool test(int w)
{
nex[N][0] = nex[N][1] = 0;
for(int i=0;i<N;++i)//can be optimized from O(N log N) to O(N) but it isnt bottleneck
{
nex[i][0] = std::lower_bound(a, a+N, a[i]+w )-a;
nex[i][1] = std::lower_bound(a, a+N, a[i]+w*2)-a;
}
memset(dp, -1, sizeof dp);
dp[0][0]=0;
for(int i=0;i<=P;++i)
for(int j=0;j<=Q;++j)
if(~dp[i][j])
{
int x=dp[i][j];
if(x==N) return 1;
if(i<P) ckmax(dp[i+1][j], nex[x][0]);
if(j<Q) ckmax(dp[i][j+1], nex[x][1]);
}
return 0;
}
int main()
{
scanf("%d%d%d", &N, &P, &Q);
for(int i=0;i<N;++i) scanf("%d", a+i);
std::sort(a, a+N);
if(P+Q>=N) return printf("1\n"),0;
int l=0,r=1e9,m;
for(;r-l>1;)
{
m=l+(r-l)/2;
if(test(m))
r=m;
else
l=m;
}
printf("%d\n", r);
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:34: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:35:28: 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);
~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
67 ms |
16128 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
68 ms |
16128 KB |
Output is correct |
4 |
Correct |
5 ms |
256 KB |
Output is correct |
5 |
Correct |
4 ms |
256 KB |
Output is correct |
6 |
Correct |
4 ms |
384 KB |
Output is correct |
7 |
Correct |
67 ms |
16128 KB |
Output is correct |
8 |
Correct |
65 ms |
16000 KB |
Output is correct |
9 |
Correct |
84 ms |
16128 KB |
Output is correct |
10 |
Correct |
65 ms |
16128 KB |
Output is correct |
11 |
Correct |
74 ms |
16248 KB |
Output is correct |
12 |
Correct |
67 ms |
16128 KB |
Output is correct |
13 |
Correct |
67 ms |
16128 KB |
Output is correct |
14 |
Correct |
65 ms |
16128 KB |
Output is correct |
15 |
Correct |
67 ms |
16128 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
73 ms |
16128 KB |
Output is correct |
2 |
Correct |
4 ms |
256 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
72 ms |
16128 KB |
Output is correct |
8 |
Correct |
78 ms |
16128 KB |
Output is correct |
9 |
Correct |
76 ms |
16128 KB |
Output is correct |
10 |
Correct |
81 ms |
16128 KB |
Output is correct |
11 |
Correct |
74 ms |
16128 KB |
Output is correct |
12 |
Correct |
109 ms |
16128 KB |
Output is correct |
13 |
Correct |
73 ms |
16128 KB |
Output is correct |
14 |
Correct |
72 ms |
16128 KB |
Output is correct |
15 |
Correct |
73 ms |
16128 KB |
Output is correct |