/*
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 2e9;
int n, p, q, k;
vector<int> a, nxt1, nxt2;
vector<vector<int>> dp;
int f(int i, int b) {
if (i == n) {
return 0;
}
if (dp[i][b] != -1) {
return dp[i][b];
}
int ret = f(nxt1[i], b) + 1;
if (b > 0) ret = min(ret, f(nxt2[i], b - 1));
return dp[i][b] = ret;
}
signed main() {
cin >> n >> p >> q;
a.resize(n);
nxt1.resize(n);
nxt2.resize(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end());
if (p + q >= n) {
cout << 1 << '\n';
return 0;
}
int lo = 1, hi = 1e9, ans = 1e9;
while (lo <= hi) {
k = (lo + hi) >> 1;
for (int i = 0; i < n; i++) {
bool ok = 0;
for (int j = i + 1; j < n; j++) {
if (a[j] > a[i] + k) {
nxt1[i] = j, ok = 1;
break;
}
}
if (!ok) {
nxt1[i] = n;
}
ok = 0;
for (int j = i + 1; j < n; j++) {
if (a[j] > a[i] + 2 * k) {
nxt2[i] = j, ok = 1;
break;
}
}
if (!ok) {
nxt2[i] = n;
}
}
dp.assign(n, vector<int>(q + 1, -1));
if (f(0, q) <= p) {
hi = k - 1, ans = k;
} else {
lo = k + 1;
}
}
cout << ans << '\n';
}
| # |
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 |
37 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
