#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> cameraFreq(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()) {
cameraFreq[pq.top().second]++;
cameraFreq[pq.top().second+pq.top().first]--;
// cout << pq.top().first << ' ' << pq.top().second << ' ' << mid << endl;
pq.pop();
QQ--;
}
for (int i = 1; i <= N+1; i++)
cameraFreq[i] += cameraFreq[i-1];
PP += QQ;
// cerr << PP << endl;
for (int i = 0; i < N; i++) {
if (!cameraFreq[i]) {
PP--;
i = lower_bound(A+i, A+N, A[i] + mid) - A - 1;
}
}
// cerr << PP << endl;
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 |
4 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
