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;
int32_t main()
{
cin.tie(0)->sync_with_stdio(0);
int n, p, q;
cin >> n >> p >> q;
vector<int> a(n + 1);
for(int i = 1; i <= n; ++i) {
cin >> a[i];
}
sort(1 + a.begin(), a.end());
auto good = [&](int x) {
int one = 1, two = 1;
vector<vector<int>> dp(n + 1, vector<int>(q + 1));
for(int i = 1; i <= n; ++i) {
while(a[i] - a[one] >= x) {
++one;
}
while(a[i] - a[two] >= x * 2) {
++two;
}
for(int j = 0; j <= q; ++j) {
dp[i][j] = dp[one - 1][j] + 1;
}
for(int j = 0; j < q; ++j) {
if(dp[i][j + 1] > dp[two - 1][j]) {
dp[i][j + 1] = dp[two - 1][j];
}
}
}
return (dp[n][q] <= p);
};
if(n <= p + q) {
cout << 1 << '\n';
exit(0);
}
int l = 1, r = 1000000000, ans = -1;
while(l <= r) {
int m = (l + r) / 2;
if(good(m)) {
r = m - 1;
ans = m;
}
else {
l = m + 1;
}
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |