#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
#define pii pair <ll, ll>
#define fi first
#define se second
const ll N = 2e3 + 5, inf = 1e18, mod = 1e9 + 7, block = 320;
int n, p, q;
int a[N];
int dp[N][N];
void reset() {
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) dp[i][j] = inf;
}
for (int i = 1; i <= p; i++) dp[0][i] = 0;
}
bool check(int mid) {
reset();
int small = 0, large = 0;
for (int i = 1; i <= n; i++) {
while(a[i] - a[small] + 1 > mid && small < i) {
small++;
}
while(a[i] - a[large] + 1 > 2 * mid && large < i) {
large++;
}
if (small >= 1) small--;
if (large >= 1) large--;
cout << small << ' ' << large << ' ' << i << '\n' << flush;
for (int j = 0; j <= p; j++) {
// cout << j << '\n' << flush;
if (j >= 1) dp[i][j] = min(dp[i][j], dp[small][j - 1]);
dp[i][j] = min(dp[i][j], dp[large][j] + 1);
}
}
for (int i = 1; i <= p; i++) {
if (dp[n][i] <= q) return true;
}
return false;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> p >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + n + 1);
int l = 1, r = 1e10, ans = 0;
// cout << 1 << '\n' << flush;
while(l <= r) {
// cout << l << ' ' << r << '\n' << flush;
int mid = (l + r) / 2;
if (check(mid)) {
// cout << mid << '\n' << flush;
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |