#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define rep(i, a, b) for (int i = (int)a; i <= (int)b; ++i)
#define rep1(i, a, b) for (int i = (int)a; i >= (int)b; --i)
#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
int n, P, Q;
vector<int> a;
const int N = 2005;
const int inf = 1e15;
int L[N][2];
int dp[N][N];
bool check(int w) {
rep(i, 0, n + 2) rep(j, 0, n + 2) {
dp[i][j] = inf;
}
rep(i, 1, n) {
L[i][0] = lower_bound(all1(a), a[i] - w + 1) - a.begin();
L[i][1] = lower_bound(all1(a), a[i] - 2 * w + 1) - a.begin();
}
// rep(i, 1, n) {
// cout << L[i][0] << ' ' << L[i][1] << '\n';
// }
rep(i, 0, P) dp[0][i] = 0;
rep(i, 1, n) rep(p, 1, P) {
dp[i][p] = min(dp[L[i][0] - 1][p - 1], dp[L[i][1] - 1][p] + 1);
//cout<<"i,p,dp="<<i<<' '<<p<<' '<<dp[i][p]<<'\n';
//if (dp[i][p] <= Q) return 1;
}
return dp[n][P] <= Q;
}
void solve() {
cin >> n >> P >> Q;
P = min(P, n);
a.resize(n + 1);
rep(i, 1, n) cin >> a[i];
sort(all1(a));
// cout << check(3) << '\n';
int l = 1, r = n, ans = 0;
while (l <= r) {
int m = (l + r) >> 1;
if (check(m)) {
ans = m, r = m - 1;
}
else l = m + 1;
}
assert(ans > 0);
cout << ans;
}
main() {
ios_base::sync_with_stdio(0); cin.tie(0);
solve();
}
Compilation message
watching.cpp:68:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
68 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
1484 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
75 ms |
64300 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
