#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;
int n, P, Q, a[N];
bool check(int mid) {
int i = 1;
int p = P, q = Q;
while (i <= n) {
int j = i, cnt1 = 0, cnt2 = 0, pq = i+1, pp = i+1;
while (p && j <= n && a[j] - a[i] <= mid - 1) j++, cnt1++, pp = j;
j = i;
while (q && j <= n && a[j] - a[i] <= 2 * mid - 1) j++, cnt2++, pq = j;
if(cnt2 == 0 && cnt1 == 0) return false;
if(cnt2 <= cnt1)
{
// use P
p--;
i = pp;
}
else
{
q--;
i = pq;
}
}
return true;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> P >> Q;
for (int i = 1; i <= n; ++i) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 1, r = 1e16, ans = -1;
while (l <= r) {
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |