#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll N = 1e5 + 5;
ll n, k, t, a[N], b[N];
bool check(vector<pll> l, vector<pll> r) {
ll il = 0, ir = 0;
while (il != l.size() - 1 || ir != r.size() - 1) {
if (il != l.size() - 1 && r[ir].first <= l[il + 1].second) il++;
else if (ir != r.size() - 1 && l[il].first >= r[ir + 1].second) ir++;
else return 0;
}
return 1;
}
bool check(ll s) {
if (s * t > 1e9) return 1;
for (ll i = 0; i < n; i++) b[i] = a[i] - 2 * s * t * i;
vector<pll> L1, L2, R1, R2;
L1 = {{b[k], b[k]}}, R1 = L1;
L2 = {{b[0], b[0]}}, R2 = {{b[n - 1], b[n - 1]}};
ll gl = max_element(b, b + k + 1) - b, gr = min_element(b + k, b + n) - b, f, x;
x = b[k];
f = 1e18;
for (ll i = k - 1; i >= gl; i--) {
f = min(f, b[i]);
if (b[i] >= x) L1.push_back({b[i], f}), f = 1e18, x = b[i];
}
x = b[k];
f = -1e18;
for (ll i = k + 1; i <= gr; i++) {
f = max(f, b[i]);
if (b[i] <= x) R1.push_back({b[i], f}), f = -1e18, x = b[i];
}
x = b[0];
f = 1e18;
for (ll i = 0; i <= gl; i++) {
f = min(f, b[i]);
if (b[i] >= x) L2.push_back({b[i], f}), f = 1e18, x = b[i];
}
x = b[n - 1];
f = -1e18;
for (ll i = n - 1; i >= gr; i--) {
f = max(f, b[i]);
if (b[i] <= x) R2.push_back({b[i], f}), f = -1e18, x = b[i];
}
return check(L1, R1) & check(L2, R2);
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> k >> t, k--;
for (ll i = 0; i < n; i++) cin >> a[i];
ll l = -1, r = 1e9 / t + 5;
check(2);
while (l + 1 < r) {
ll m = (l + r) / 2;
(check(m) ? r : l) = m;
}
cout << r;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |