#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int MOD = 998244353;
void solve(){
int n, p, q; cin >> n >> p >> q;
swap(p, q);
vector<int> v(n);
for(auto &i : v) cin >> i;
sort(v.begin(), v.end());
if(n <= p + q){
cout << 1 << endl; return;
}
set<pair<int, int>> s;
for(int i = 0; i < n; i++) s.insert({v[i], i});
int ans;
ll lo = 1;
ll hi = 9;
while(lo <= hi){
ll w = (lo + hi) / 2;
vector<vector<int>> dp(n, vector<int>(p + 1, 1e9));
for(int i = 0; i < n; i++){
auto it = s.upper_bound({v[i] - w, 1e9});
if(it == s.begin()){
dp[i] = vector<int>(p + 1, 1);
}else{
it--;
int j = (*it).second;
dp[i] = dp[j];
for(int g = 0; g <= p; g++) dp[i][g]++;
}
it = s.upper_bound({v[i] - 2 * w, 1e9});
if(it == s.begin()){
for(int g = 1; g <= p; g++) dp[i][g] = 0;
}else{
it--;
int j = (*it).second;
for(int g = 1; g <= p; g++){
dp[i][g] = min(dp[i][g], dp[j][g - 1]);
}
}
}
if(dp[n - 1][p] <= q){
ans = w;
hi = w - 1;
}else lo = w + 1;
}
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//freopen("inpt.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
//int tt; cin >> tt;
int tt = 1;
for(int t = 1; t <= tt; t++){
solve();
}
}
Compilation message
watching.cpp: In function 'void solve()':
watching.cpp:6:14: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
6 | #define endl "\n"
| ^~~~
watching.cpp:21:6: note: 'ans' was declared here
21 | int ans;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
