#include <bits/stdc++.h>
using namespace std;
#define maxn 2002
const int inf = 1000000000;
int N, P, Q;
vector<int> nums;
int dp[maxn][maxn];
bool go(int mid) {
//option is to end at me with a small or end at me with a large
//we will just consider ending exactly at some guy (e.g. the last guy)
dp[0][0] = 0;
int pbef = 0;
int qbef = 0;
for (int i = 1 ; i <= N; i++) {
while (nums[i] - nums[pbef+1] >= mid) {
pbef++;
}
while (nums[i] - nums[qbef+1] >= 2*mid) {
qbef++;
}
for (int j = 0; j <= i && j <= P; j++) {
dp[i][j] = inf;
if (j > 0) dp[i][j] = min(dp[i][j], dp[pbef][j-1]);
dp[i][j] = min(dp[i][j], dp[qbef][j]+1);
}
}
for (int i = 0; i <= P; i++) {
if (dp[N][i] <= Q) return true;
}
return false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
for (int i = 0; i < maxn; i++) {
for (int j = 0; j < maxn; j++) dp[i][j] = inf;
}
cin >> N >> P >> Q;
if (P + Q >= N) return 1;
int cur;
for (int i = 0; i < N; i++) {
cin >> cur;
nums.push_back(cur);
}
nums.push_back(-1);
nums.push_back(cur);
sort(nums.begin(), nums.end());
int lo = 1, hi = inf;
while (lo < hi) {
int mid = (lo+hi)/2;
if (go(mid)) {
hi = mid;
}
else lo = mid+1;
}
cout << lo << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
16248 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
16296 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
