#include <bits/stdc++.h>
#define MN 2071
using namespace std;
using ll = long long;
ll n, p, q, A[MN], DP[MN][MN];
bool ok(int len) {
if(p + q >= n) return 1;
///DP[poz][nr_mici]
int lsmall = 1, lbig = 1;
DP[1][0] = 1;
DP[1][1] = 0;
for(int i = 1; i <= n; ++i) {
while(A[i] - A[lsmall] >= len) ++lsmall;
while(A[i] - A[lbig] >= 2 * len) ++lbig;
for(int j = 0; j <= min(p, n); ++j)
DP[i][j] = min((!!j) * DP[lsmall-1][j-1] + (!j) * INT_MAX, DP[lbig-1][j] + 1);
}
return DP[n][p] <= q;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n >> p >> q;
for(int i = 1; i <= n; ++i) cin >> A[i];
ll st = 1, dr = 1e9, mij;
while(st < dr) {
mij = (st + dr) >> 1;
if(ok(mij)) dr = mij;
else st = mij + 1;
}
cout << st << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
