#include <bits/stdc++.h>
using namespace std;
const int N = 2020;
int n, p, q, a[N];
int dp[N][N];
void Max(int &a, int b) { a = (a < b ? b : a); }
bool Check(int w) {
memset(dp, 0, sizeof dp);
int total = min(n, p + q);
for (int i = 0; i < total; ++i) {
for (int np = 0; np <= min(i, p); ++np) {
int x = dp[i][np];
int nq = i - np;
if (x == n) {
return true;
}
if (np < p) {
int nxt = lower_bound(a, a + n, a[x] + w) - a;
Max(dp[i + 1][np + 1], nxt);
}
if (nq < q) {
int nxt = lower_bound(a, a + n, a[x] + w + w) - a;
Max(dp[i + 1][np], nxt);
}
}
}
return dp[total][p] >= n;
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> p >> q;
p = min(p, n), q = min(q, n);
for (int i = 0; i < n; ++i) cin >> a[i];
sort(a, a + n);
int l = 0, r = 1e9, cur = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (Check(mid)) {
cur = mid;
r = mid - 1;
} else l = mid + 1;
}
cout << cur << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
61 ms |
16204 KB |
Output is correct |
2 |
Correct |
62 ms |
16228 KB |
Output is correct |
3 |
Correct |
66 ms |
16196 KB |
Output is correct |
4 |
Correct |
68 ms |
16264 KB |
Output is correct |
5 |
Correct |
63 ms |
16268 KB |
Output is correct |
6 |
Correct |
70 ms |
16204 KB |
Output is correct |
7 |
Correct |
67 ms |
16312 KB |
Output is correct |
8 |
Correct |
63 ms |
16268 KB |
Output is correct |
9 |
Correct |
65 ms |
16332 KB |
Output is correct |
10 |
Correct |
65 ms |
16204 KB |
Output is correct |
11 |
Correct |
63 ms |
16164 KB |
Output is correct |
12 |
Correct |
67 ms |
16268 KB |
Output is correct |
13 |
Correct |
64 ms |
16204 KB |
Output is correct |
14 |
Correct |
63 ms |
16192 KB |
Output is correct |
15 |
Correct |
62 ms |
16204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
65 ms |
16204 KB |
Output is correct |
2 |
Correct |
60 ms |
16272 KB |
Output is correct |
3 |
Correct |
906 ms |
16296 KB |
Output is correct |
4 |
Execution timed out |
1076 ms |
16204 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |