#include <bits/stdc++.h>
#define INF 1000000007
#define pb push_back
#define int long long
#define ub upper_bound
using namespace std;
int n,p,q,a[2001],S[2001],B[2001],dp[2001][2001];
bool legit(int W) {
for (int i = 0 ; i < n ; i ++) {
S[i]=ub(a,a+n,a[i]+W-1)-a;
B[i]=ub(a,a+n,a[i]+2*W-1)-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]!=-1) {
if (dp[i][j]==n) return true;
dp[i+1][j]=max(dp[i+1][j],S[dp[i][j]]);
dp[i][j+1]=max(dp[i][j+1],B[dp[i][j]]);
}
return false;
}
signed main() {
cin >> n>>p>>q;
for (int i = 0 ; i < n ; i ++) cin>>a[i];
if (p+q>=n) {cout<<"1"; return 0;}
sort(a,a+n);
int L = 1 ,R = 1000000000;
while(L <= R){
if (L == R)break;
int M = L + (R-L)/2;
if(legit(M)) R = M;
else L = M + 1;
}
cout << L;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
233 ms |
31736 KB |
Output is correct |
2 |
Correct |
2 ms |
31736 KB |
Output is correct |
3 |
Correct |
226 ms |
31928 KB |
Output is correct |
4 |
Correct |
2 ms |
31928 KB |
Output is correct |
5 |
Correct |
2 ms |
31928 KB |
Output is correct |
6 |
Correct |
2 ms |
31928 KB |
Output is correct |
7 |
Correct |
230 ms |
31928 KB |
Output is correct |
8 |
Correct |
244 ms |
32052 KB |
Output is correct |
9 |
Correct |
221 ms |
32052 KB |
Output is correct |
10 |
Correct |
232 ms |
32052 KB |
Output is correct |
11 |
Correct |
209 ms |
32068 KB |
Output is correct |
12 |
Correct |
210 ms |
32068 KB |
Output is correct |
13 |
Correct |
215 ms |
32068 KB |
Output is correct |
14 |
Correct |
224 ms |
32068 KB |
Output is correct |
15 |
Correct |
230 ms |
32068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
230 ms |
32068 KB |
Output is correct |
2 |
Correct |
2 ms |
32068 KB |
Output is correct |
3 |
Correct |
3 ms |
32068 KB |
Output is correct |
4 |
Correct |
3 ms |
32068 KB |
Output is correct |
5 |
Correct |
3 ms |
32068 KB |
Output is correct |
6 |
Correct |
3 ms |
32068 KB |
Output is correct |
7 |
Correct |
222 ms |
32100 KB |
Output is correct |
8 |
Correct |
268 ms |
32100 KB |
Output is correct |
9 |
Correct |
258 ms |
32100 KB |
Output is correct |
10 |
Correct |
237 ms |
32100 KB |
Output is correct |
11 |
Correct |
232 ms |
32100 KB |
Output is correct |
12 |
Correct |
309 ms |
32100 KB |
Output is correct |
13 |
Correct |
232 ms |
32124 KB |
Output is correct |
14 |
Correct |
225 ms |
32124 KB |
Output is correct |
15 |
Correct |
236 ms |
32124 KB |
Output is correct |