This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[2001][2001];
vector<int> v;
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n, p, q;
cin >> n >> p >> q;
if (p + q >= n) {
cout << 1;
return 0;
}
int low = 0;
int high = 0;
vector<int> v;
for (int i = 0; i < n; i++) {
int a;
cin >> a;
v.push_back(a);
high = max(high, a);
}
sort(v.begin(), v.end());
while (high - low > 1) {
memset(dp, 0, sizeof dp);
int mid = (high + low) / 2;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= p; j++) {
int a = upper_bound(v.begin(), v.end(), v[i] + 2 * mid - 1) - v.begin();
dp[i][j] = dp[a][j] + 1;
if (j != 0) {
int b = upper_bound(v.begin(), v.end(), v[i] + mid - 1) - v.begin();
dp[i][j] = min(dp[i][j], dp[b][j - 1]);
}
}
}
int ans = LLONG_MAX;
for (int i = 0; i <= p; i++) {
ans = min(ans, dp[0][i]);
}
if (ans <= q) {
high = mid;
} else {
low = mid;
}
}
cout << high;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |