#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[2001], dp[2001][2001], posp[2001] , posq[2001], n , p , q;
int check(int w)
{
memset(dp , - 1, sizeof(dp));
for(int i = 0 ; i < n ; ++i)
{
posp[i] = upper_bound(a,a + n,a[i] + w - 1) - a;
posq[i] = upper_bound(a,a + n,a[i] + w * 2 - 1) - a;
}
dp[0][0] = 0;
for(int i = 0 ; i <= p ; ++i)
{
for(int j = 0 ; j <= q ; ++j)
{
if(dp[i][j] >= 0)
{
if(dp[i][j] >= n) return 1;
dp[i + 1][j] = max(dp[i + 1][j], posp[dp[i][j]]);
dp[i][j + 1] = max(dp[i][j + 1], posq[dp[i][j]]);
}
}
}
return 0;
}
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
//a
signed main(){
cin >> n >> p >> q;
for(int i = 0 ; i < n ; ++i)
cin >> a[i];
sort(a, a + n);
int l = 1, r = 1e9, mid = (l + r) / 2;
while(l != r)
{
if(check(mid) == 1) r = mid;
else l = mid + 1;
mid = (l + r) / 2;
}
cout << l;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
230 ms |
31608 KB |
Output is correct |
| 2 |
Correct |
235 ms |
31844 KB |
Output is correct |
| 3 |
Correct |
221 ms |
31844 KB |
Output is correct |
| 4 |
Correct |
221 ms |
31844 KB |
Output is correct |
| 5 |
Correct |
236 ms |
31856 KB |
Output is correct |
| 6 |
Correct |
230 ms |
31996 KB |
Output is correct |
| 7 |
Correct |
213 ms |
31996 KB |
Output is correct |
| 8 |
Correct |
188 ms |
31996 KB |
Output is correct |
| 9 |
Correct |
198 ms |
31996 KB |
Output is correct |
| 10 |
Correct |
225 ms |
31996 KB |
Output is correct |
| 11 |
Correct |
236 ms |
32000 KB |
Output is correct |
| 12 |
Correct |
223 ms |
32000 KB |
Output is correct |
| 13 |
Correct |
192 ms |
32000 KB |
Output is correct |
| 14 |
Correct |
196 ms |
32000 KB |
Output is correct |
| 15 |
Correct |
205 ms |
32000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
217 ms |
32064 KB |
Output is correct |
| 2 |
Correct |
211 ms |
32064 KB |
Output is correct |
| 3 |
Correct |
262 ms |
32064 KB |
Output is correct |
| 4 |
Correct |
237 ms |
32064 KB |
Output is correct |
| 5 |
Correct |
223 ms |
32064 KB |
Output is correct |
| 6 |
Correct |
224 ms |
32064 KB |
Output is correct |
| 7 |
Correct |
246 ms |
32064 KB |
Output is correct |
| 8 |
Correct |
244 ms |
32064 KB |
Output is correct |
| 9 |
Correct |
220 ms |
32064 KB |
Output is correct |
| 10 |
Correct |
227 ms |
32104 KB |
Output is correct |
| 11 |
Correct |
235 ms |
32104 KB |
Output is correct |
| 12 |
Correct |
288 ms |
32104 KB |
Output is correct |
| 13 |
Correct |
229 ms |
32124 KB |
Output is correct |
| 14 |
Correct |
218 ms |
32124 KB |
Output is correct |
| 15 |
Correct |
224 ms |
32124 KB |
Output is correct |
