#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 1000000000
int n, p, q;
vector<int> a;
int main(){
cin>>n>>p>>q;
a.assign(n + 1, 0);
for (int i = 1; i <= n; i++){
cin>>a[i];
}
sort(a.begin(), a.end());
if (n <= p + q){
cout<<1;
return 0;
}
ll dp[n + 1][p + q + 1];
int l = 1, r = 1000000000, w = -1;
while (l <= r){
int mid = (l + r) / 2;
for (int i = 0; i <= n; i++){
for (int j = 0; j <= p + q; j++){
dp[i][j] = 0;
}
}
for (int j = 0; j <= p + q; j++){
dp[0][j] = 1;
}
for (int i = 1; i <= n; i++){
for (int j = 0; j <= p + q; j++){
if (i <= p + q){
dp[i][j] = 1;
continue;
}
for (int k = i - 1; k >= 0; k--){
if (a[i] - a[k + 1] + 1 <= 2 * mid && j != 0) dp[i][j] = max(dp[i][j], dp[k + 1][j - 1]);
if (a[i] - a[k + 1] + 1 <= mid && j != p + q) dp[i][j] = max(dp[i][j], dp[k + 1][j]);
if (a[i] - a[k] + 1 > 2 * mid) break;
}
}
}
if (dp[n][q] == 1){
r = mid - 1;
w = mid;
}
else{
l = mid + 1;
}
}
cout<<w;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
