#include <bits/stdc++.h>
#define ll long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
const int N = 222;
bool dp[N][N][N];
int a[N];
void solve() {
int n, p, q;
cin >> n >> p >> q;
for (int i = 1; i <= n; i++)
cin >> a[i];
sort(a + 1, a + n + 1);
if (p + q >= n) {
cout << 1 << '\n';
return;
}
auto check = [&](int w) -> bool {
memset(dp, 0, sizeof(dp));
for (int i = 0; i <= p; i++)
for (int j = 0; j <= q; j++)
dp[0][i][j] = 1;
int j0 = 0, j1 = 0;
for (int i = 1; i <= n; i++) {
// place w.
while (j0 + 1 <= n && a[j0 + 1] - a[i] + 1 <= w)
j0++;
while (j1 + 1 <= n && a[j1 + 1] - a[i] + 1 <= 2*w)
j1++;
for (int lp = 0; lp <= p; lp++)
for (int lq = 0; lq <= q; lq++)
dp[j0][lp][lq] |= dp[i-1][lp + 1][lq];
for (int lp = 0; lp <= p; lp++)
for (int lq = 0; lq <= q; lq++)
dp[j1][lp][lq] |= dp[i-1][lp][lq + 1];
}
return dp[n][0][0];
};
int l = 0, r = 1e9 + 128;
while (l + 1 < r) {
int m = (l + r) >> 1;
if (check(m))
r = m;
else
l = m;
}
cout << r << '\n';
}
main() {
boost;
solve();
return 0;
}
Compilation message
watching.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
66 | main() {
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
11100 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
7 ms |
11096 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
9 ms |
11100 KB |
Output is correct |
8 |
Correct |
8 ms |
11096 KB |
Output is correct |
9 |
Correct |
8 ms |
11100 KB |
Output is correct |
10 |
Correct |
10 ms |
11100 KB |
Output is correct |
11 |
Correct |
13 ms |
11164 KB |
Output is correct |
12 |
Correct |
16 ms |
10964 KB |
Output is correct |
13 |
Correct |
7 ms |
11100 KB |
Output is correct |
14 |
Correct |
9 ms |
11100 KB |
Output is correct |
15 |
Correct |
8 ms |
11100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
22108 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |