#include "bits/stdc++.h"
using namespace std;
//#include "debug.h"
void solve() {
int n, p, q;
cin >> n >> p >> q;
p = min(p, n);
q = min(q, n);
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
std::sort(a.begin(), a.end());
vector<int> go(n), go2(n);
auto upd = [&] (int pos, int w) {
if (pos == n) {
return n;
}
// debug(a, pos, w);
return w == 1 ? go[pos] : go2[pos];
};
auto check = [&] (int w) -> bool {
if (w * 1ll * p + 2ll * w * q >= n) {
return true;
}
for (int pos = 0; pos < n; pos++) {
go[pos] = int(std::lower_bound(a.begin(), a.end(), a[pos] + w) - a.begin());
go2[pos] = int(std::lower_bound(a.begin(), a.end(), a[pos] + 2 * w) - a.begin());
}
vector<vector<int>> mx(p + 1, vector<int> (q + 1));
for (int i = 0; i <= p; i++) {
for (int j = 0; j <= q; j++) {
if (i + 1 <= p) {
mx[i + 1][j] = max(mx[i + 1][j], upd(mx[i][j], 1));
}
if (j + 1 <= q) {
mx[i][j + 1] = max(mx[i][j + 1], upd(mx[i][j], 2));
}
}
}
// debug(w, mx);
return mx[p][q] == n;
};
int l = 0, r = (int) 1e9;
while (l + 1 < r) {
int m = (l + r) / 2;
if (check(m)) {
r = m;
} else {
l = m;
}
}
cout << r << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
// cin >> t;
while (t--) {
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
