#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxN = 2e3+10;
int A[mxN], N, P, Q;
bool ok(ll mid) {
priority_queue<pair<int, int>> pq;
vector<int> covered(N+10, 0);
for (int i = 0; i < N; i++) {
int can = lower_bound(A+i, A+N, A[i] + mid*2) - (A+i);
// cerr << i << ' ' << can << ' ' << mid << endl;
pq.push({can, i});
}
int PP = P, QQ = Q;
while(QQ && !pq.empty()) {
if (!covered[pq.top().second]) {
for (int i = pq.top().second; i < pq.top().second+pq.top().first; i++)
covered[i] = 1;
QQ--;
}
pq.pop();
}
for (int i = 0; i < N; i++) {
if (!covered[i]) {
PP--;
int ii = i;
while(ii < N && A[ii] < A[i] + mid)
covered[ii++] = 1;
}
}
return PP >= 0;
}
void solve() {
cin >> N >> P >> Q;
for (int i = 0; i < N; i++)
cin >> A[i];
sort(A, A+N);
ll l = 1, r = 1e10, mid;
while(l < r) {
mid = (l+r) >> 1;
if (ok(mid)) r = mid;
else l = mid+1;
}
cout << r << endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
| # |
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 |
3 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
