#include<bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
long long n,p,q;cin>>n>>p>>q;
vector<long long>arr(n);
for (long long i = 0;i<n;++i)cin>>arr[i];
sort(arr.begin(),arr.end());
long long left = 0,right = 1e10;
if (p + q >=n){
cout<<1<<'\n';
return 0;
}
long long ans = right;
function<bool(long long)>check = [&](long long u){
vector<vector<pair<int,int>>>adj(n);
p = min(p,n);
vector<vector<long long>>dp(n + 1,vector<long long>(p + 1,INT_MAX));
dp[0][0] = 0;
for (int i = 0;i<n;++i){
long long nxt = lower_bound(arr.begin(),arr.end(),arr[i] + 2 * u) - arr.begin();
long long nxt2 = lower_bound(arr.begin(),arr.end(),arr[i] + u) - arr.begin();
for (int j = 0;j<=p;++j){
dp[nxt][j] = min(dp[i][j] + 1,dp[nxt][j]);
if (j + 1<=p)
dp[nxt2][j + 1] = min(dp[i][j],dp[nxt2][j]);
}
}
for (int i = 0;i<=p;++i){
if (dp[n][i]<=q)return true;
}
return false;
};
while(left<right){
long long mid = (left + right)>>1;
if (check(mid)){
right = mid;
ans = mid;
}
else{
left = mid + 1;
}
}
cout<<left<<'\n';
return 0;
}
Compilation message
watching.cpp: In function 'int main()':
watching.cpp:16:12: warning: variable 'ans' set but not used [-Wunused-but-set-variable]
16 | long long ans = right;
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
5 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
