#include <bits/stdc++.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, p, q;
std::cin >> n >> p >> q;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
if (p + q >= n) {
std::cout << 1 << "\n";
return 0;
}
sort(a.begin(), a.end());
auto check = [&](int len) {
std::vector<int> v = a;
for (int it = 0; it < q; it++) {
std::vector<int> t(v.size());
std::pair<int, int> mx = {0, 0};
int m = -1;
for (int i = 0, j = 0; i < int(v.size()); i++) {
while (v[i] - v[j] >= 2 * len) j++;
if (m < i - j) {
m = i - j;
mx = {j, i};
}
}
v.erase(v.begin() + mx.first, v.begin() + mx.second + 1);
// for (auto x : v) {
// std::cout << x << " \n"[x == v.back()];
// }
if (v.empty()) {
return 1;
}
}
int n = v.size();
std::vector<std::vector<int>> dp(n + 1, std::vector<int>(p + 1));
dp[0][0] = 1;
int p1 = 1;
for (int i = 1; i <= n; i++) {
while (a[i - 1] - a[p1 - 1] >= len) p1++;
for (int P = 0; P <= p; P++) {
for (int Q = 0; Q <= q; Q++) {
if (P) {
dp[i][P] += dp[i][P - 1];
dp[i][P] += dp[p1 - 1][P - 1];
}
}
}
}
return dp[n][p];
};
// std::cout << check(3) << "\n";
// return 0;
int l = 0, r = 1000000007;
while (l + 1 < r) {
int mid = (l + r) / 2;
if (check(mid)) {
r = mid;
} else {
l = mid;
}
}
std::cout << r << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
