#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define base 101
using namespace std;
const ll mxN = 2005;
const ll mx = 1e5 + 5;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
int n,p,q;
ll dp[mxN][mxN];
vector<ll> a;
int res;
bool check(int x){
memset(dp,-1,sizeof(dp));
for(int i = 0;i <= p; i++){
for(int j = 0;j <= q;j++){
if(i == 0 && j == 0) continue;
ll i1 = dp[i][j-1] + 1;
ll i2 = dp[i-1][j] + 1;
ll cur1 = a[i1] + (2*x) - 1;
ll cur2 = a[i2] + x - 1;
ll k1 = upper_bound(a.begin(),a.end(),cur1) - a.begin() - 1;
ll k2 = upper_bound(a.begin(),a.end(),cur2) - a.begin() - 1;
if(i == 0) dp[i][j] = k1;
else if(j == 0) dp[i][j] = k2;
else dp[i][j] = max(k1,k2);
if(dp[i][j] >= n-1) return true;
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin>>n>>p>>q;
for(int i = 0;i < n;i++){
cin>>a[i];
}
int l = 1,r = 1e9;
res = r;
p = min(p,n);
q = min(q,n);
if(p+q >= n){
cout<<1;
return 0;
}
sort(a.begin(),a.end());
while(l <= r){
int mid = (l + r)/2;
if(check(mid)){
res = min(res,mid);
r = mid - 1;
}
else l = mid + 1;
}
cout<<res;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
488 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
