#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vint vector <int>
#define vll vector <ll>
#define vbool vector<bool>
#define pairint pair<int,int>
#define pairll pair<ll,ll>
#define fi first
#define sc second
#define rever greater<ll>()
using namespace std;
bool func(ll &n, vll &a, ll &x, ll &y, ll r){
vector<vll> dp(x+1, vll(y+1));
for(int i = 1; i <= x; i++){
for(int k = dp[i-1][0]+1; k <= n; k++){
if(a[k] - a[dp[i-1][0]+1] < r){
dp[i][0] = k;
}else{
break;
}
}
} if(dp[x][0] == n) return true;
for(int i = 1; i <= y; i++){
for(int k = dp[0][i-1]+1; k <= n; k++){
if(a[k] - a[dp[0][i-1]+1] < r*2){
dp[0][i] = k;
}else{
break;
}
}
} if(dp[0][y] == n) return true;
ll mx;
for(int i = 1; i <= x; i++){
for(int j = 1; j <= y; j++){
for(int k = dp[i-1][j]+1; k <= n; k++){
if(a[k] - a[dp[i-1][j]+1] < r){
mx = k;
}else{
break;
}
} dp[i][j] = mx;
for(int k = dp[i][j-1]+1; k <= n; k++){
if(a[k] - a[dp[i][j-1]+1] < r*2){
mx = k;
}else{
break;
}
} dp[i][j] = max(dp[i][j], mx);
if(dp[i][j] == n) return true;
}
}return false;
}
void solve(ll tc){
ll n, x, y; cin >> n >> x >> y;
vll a(n+1);
for(int i = 1; i <= n; i++){
cin >> a[i];
} sort(a.begin(), a.end());
if(x+y >= n){
cout << 1 << endl; return;
}
ll l = 1, r = a[n], mid;
bool ans;
while(l < r){
mid = (l+r)/2;
ans = func(n, a, x, y, mid);
if(ans){
r = mid;
}else{
l = mid;
}
if((l+r)/2 == mid){
if(func(n, a, x, y, l)){
r = l;
} break;
}
}
cout << r << endl;
}
int main(){
ll t; t = 1;
for(int i = 1; i <= t; i++){
solve(i);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |