# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1246931 | King87arshia | 구경하기 (JOI13_watching) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std;
const int N = 2e3 + 5, inf = 1e9 + 5;
int a[N], q, n, p;
bool check(int mid) {
int dp[n + 5][q + 5];
memset(dp, 63, sizeof dp);
dp[0][0] = 0;
int id = 0, id2 = 0;
for (int i = 0; i < n; i++) {
while (id < n && a[id] - a[i] < mid)
id++;
while (id2 < n && a[id2] - a[i] < 2 * mid)
id2++;
for (int j = 0; j <= q; j++) {
if (j < q)
dp[id2][j + 1] = min(dp[id2][j + 1], dp[i][j]);
dp[id][j] = min(dp[id][j], dp[i][j] + 1);
}
}
for (int i = 0; i <= q; i++)
if (dp[n][i] <= p)
return true;
return false;
}
int main() {
cin >> n >> p >> q;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
if (p + q >= n) {
cout << 1:
return 0;
}
int l = 0, r = 1e9 + 5;
while (r - l > 1) {
int mid = l + r >> 1;
if (check(mid))
r = mid;
else
l = mid;
}
cout << r;
}