#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define v(a) vector<a>
#define all(x) x.begin(), x.end()
#define trace2(x,y) cout<<"> "<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<endl
#define trace3(x,y,z) cout<<"> "<<#x<<" : "<<x<<" | "<<#y<<" : "<<y<<" | "<<#z<<" : "<<z<<endl
template<typename T>
void print(vector<T> var) { // print vector
for(auto i : var) {
cout << i << ' ';
} cout << endl;
}
v(v(ll)) dp;
v(ll) arr, nextP, nextQ;
ll n, p, q;
ll trav(ll idx, ll cur, ll k){
if(idx >= n) return 1;
if(cur < 0) return 1e9;
if(dp[idx][cur] != -1) return dp[idx][cur];
// trace2(nextP, nextQ);
// trace2(idx, k);
ll ret = 1e9;
ret = min(trav(nextP[idx], cur, k)+1, trav(nextQ[idx], cur-1, k));
return dp[idx][cur] = ret;
}
ll binsearch(ll l, ll r){
if(l <= r){
ll mid = (l+r)/2;
nextP.assign(n, n);
nextQ.assign(n, n);
for(int i = 0; i < n; i++){
bool ok1 = false, ok2 = false;
ll op = arr[i]+mid, oq = arr[i]+2*mid;
for(int j = i+1; j < n; j++){
if(ok1 && ok2) break;
if(arr[j] > op && !ok1){
nextP[i] = j;
ok1 = true;
}
if(arr[j] > oq && !ok2){
nextQ[i] = j;
ok2 = true;
}
}
}
// print(nextP);
// print(nextQ);
ll temp = trav(0, q, mid);
for(int i = 0; i < n; i++){
dp[i].clear();
dp[i].assign(q+1, -1);
}
if(temp <= p){
return min(mid, binsearch(l, mid-1));
}
return binsearch(mid+1, r);
}
}
int main(){
cin >> n >> p >> q;
arr.resize(n);
for(int i = 0; i < n; i++) cin >> arr[i];
if(p+q >= n) cout << 1 << endl;
else {
p = min(p, n);
q = min(q, n);
dp.resize(n+5);
for(int i = 0; i < n; i++) dp[i].assign(q+5, -1);
sort(arr.begin(), arr.end());
cout << binsearch(1, 1e9);
}
}
Compilation message
watching.cpp: In function 'long long int binsearch(long long int, long long int)':
watching.cpp:67:1: warning: control reaches end of non-void function [-Wreturn-type]
67 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1053 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1008 ms |
856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
