#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const int MAXN = 100005;
const i128 inf = 1e36;
i128 val[MAXN], inlm[MAXN], inrm[MAXN], oulm[MAXN], ourm[MAXN];
ll pos[MAXN], T;
int inl[MAXN], inr[MAXN], oul[MAXN], our[MAXN], N, K;
ll cdiv(ll a, ll b){
return (a + b - 1) / b;
}
bool test(ll v){
for (int i = 1; i <= N; i++) val[i] = pos[i] - (i128)(2) * v * T * i;
int bl, br;
vector<pair<i128, int>> st;
for (int i = 1; i <= K; i++){
while (!st.empty() && st.back().first < val[i]) st.pop_back();
if (!st.empty()) oul[i] = st.back().second;
st.push_back({val[i], i});
}
bl = st[0].second; st.clear();
for (int i = N; i >= K; i--){
while (!st.empty() && st.back().first > val[i]) st.pop_back();
if (!st.empty()) our[i] = st.back().second;
st.push_back({val[i], i});
}
br = st[0].second; st.clear();
for (int i = K; i >= 1; i--){
while (!st.empty() && st.back().first < val[i]) st.pop_back();
if (!st.empty()) inl[i] = st.back().second;
st.push_back({val[i], i});
}
st.clear();
for (int i = K; i <= N; i++){
while (!st.empty() && st.back().first > val[i]) st.pop_back();
if (!st.empty()) inr[i] = st.back().second;
st.push_back({val[i], i});
}
st.clear();
i128 mv = inf;
for (int i = K; i >= 1; i--){
mv = min(mv, val[i]); oulm[i] = mv;
}
mv = -inf;
for (int i = K; i <= N; i++){
mv = max(mv, val[i]); ourm[i] = mv;
}
mv = inf;
for (int i = 1; i <= K; i++){
mv = min(mv, val[i]); inlm[i] = mv;
}
mv = -inf;
for (int i = N; i >= K; i--){
mv = max(mv, val[i]); inrm[i] = mv;
}
int l = K, r = K;
while (l != bl || r != br){
bool ok = 0;
if (l != bl){
int nl = oul[l];
if (oulm[nl] >= val[r]){
ok = 1; l = nl;
}
}
if (!ok && r != br){
int nr = our[r];
if (val[l] >= ourm[nr]){
ok = 1; r = nr;
}
}
if (!ok) return 0;
}
if (val[1] < val[N]) return 0;
l = 1, r = N;
while (l != bl || r != br){
bool ok = 0;
if (l != bl){
int nl = inl[l];
if (inlm[nl] >= val[r]){
ok = 1; l = nl;
}
}
if (!ok && r != br){
int nr = inr[r];
if (val[l] >= inrm[nr]){
ok = 1; r = nr;
}
}
if (!ok) return 0;
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> N >> K >> T;
for (int i = 1; i <= N; i++) cin >> pos[i];
ll lo = 1, hi = 1e9, ans;
while (lo <= hi){
ll m = (lo + hi) >> 1;
if (test(m)){
ans = m; hi = m - 1;
}
else lo = m + 1;
}
cout << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |