#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v(a) vector<a>
template<typename T>
void print(vector<T> var) { // print vector
for(auto i : var) {
cout << i << ' ';
} cout << endl;
}
ll n, p, q;
v(v(ll)) dp;
v(ll) arr, nextP, nextQ;
ll trav(ll idx, ll cur){
if(idx >= n) return 0;
if(cur < 0) return 1e9;
if(dp[idx][cur] != -1) return dp[idx][cur];
ll ret = 1e9;
ret = trav(nextP[idx], cur)+1;
if(cur > 0) ret = min(ret, trav(nextQ[idx], cur-1));
return dp[idx][cur] = ret;
}
ll binsearch(ll l, ll r){
if(l <= r){
ll mid = (l+r)/2;
nextP.clear();
nextQ.clear();
nextP.assign(n+1, n);
nextQ.assign(n+1, n);
// nextP
// cout << mid << endl;
for(int i = 0; i < n; i++){
ll cur = arr[i]+mid;
for(int j = i+1; j < n; j++){
if(arr[j] > cur){
nextP[i] = j;
break;
}
}
}
// nextQ
for(int i = 0; i < n; i++){
ll cur = arr[i]+2*mid;
for(int j = i+1; j < n; j++){
if(arr[j] > cur){
nextQ[i] = j;
break;
}
}
}
// print(nextP);
// print(nextQ);
//reset DP
for(int i = 0; i < n; i++){
dp[i].clear();
dp[i].assign(q+1, -1);
}
if(trav(0, q) <= p) return min(mid, binsearch(l, mid-1));
return binsearch(mid+1, r);
}
return 1e9;
}
int main(){
cin >> n >> p >> q;
dp.resize(n+5);
arr.resize(n);
for(int i = 0; i < n; i++) cin >> arr[i];
sort(arr.begin(), arr.end());
if(p + q >= n) cout << 1;
else {
// p = min(p, n);
q = min(q, n);
cout << binsearch(1, 1e9);
}
}
| # |
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 |
50 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
