# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1168013 | tsengang | 구경하기 (JOI13_watching) | C11 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ertunt return
#define vodka void
using namespace std;
int main() {
ll n, p, q;
cin >> n >> p >> q;
if (p + q >= n) {
cout << 1;
ertunt 0;
}
ll a[n];
for (ll i = 0; i < n; i++) cin >> a[i];
ll l = 1, r = 1e9 + 5;
while (l < r) {
ll m = (l + r) / 2;
ll dp[n + 4][p + 1][q + 1] = {};
for (ll i = n - 1; i >= 0; i--) {
for (ll j = p; j >= 0; j--) {
for (ll k = q; k >= 0; k--) {
if (k > 0) {
ll cur = i;
while (cur < n - 1 and a[cur + 1] < a[i] + 2 * m) cur++;
if (cur == n - 1) {
dp[i][j][k] = 1;
continue;
}
dp[i][j][k] = max(dp[cur + 1][j][k - 1], dp[i][j][k]);
}
if (j > 0) {
ll cur = i;
while (cur < n - 1 and a[cur + 1] < a[i] + m) cur++;
if (cur == n - 1) {
dp[i][j][k] = 1;
continue;
}
dp[i][j][k] = max(dp[cur + 1][j - 1][k], dp[i][j][k]);
}
}
}
}
if (dp[0][p][q] == 1) r = m;
else l = m + 1;
}
cout << l;
}