#include <bits/stdc++.h>
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) ((int) x.size())
#define ld long double
using namespace std;
const int N = 1e5 + 111, INF = 1e9 + 111;
int n, k, t, X[N];
vector <ld> a[2], ps[2];
int p[2] = {0, 0}, nxt[2] = {0, 0};
ld mn[2] = {-INF, -INF};
bool flag;
int g(int x) {
return ps[x][p[x]];
}
void find_next(int x) {
nxt[x] = -1;
mn[x] = INF;
int np = p[x] + 1;
while (np < n && (ps[x][np] < g(x) || (flag == 0 && ps[x][np] == g(x)))) {
mn[x] = min(mn[x], ps[x][np]);
np++;
}
if (np < n) nxt[x] = np;
}
bool check2() {
for (int i = 0; i < 2; i++) {
p[i] = nxt[i] = mn[i] = 0;
}
if (g(0) + g(1) < 0) return 0;
find_next(0);
find_next(1);
while (nxt[0] != -1 || nxt[1] != -1) {
if (nxt[0] != -1 && mn[0] + g(1) >= 0) {
p[0] = nxt[0];
find_next(0);
continue;
}
if (nxt[1] != -1 && mn[1] + g(0) >= 0) {
p[1] = nxt[1];
find_next(1);
continue;
}
return 0;
}
return 1;
}
bool check(int s) {
for (int i = 0; i < n; i++) {
a[i].clear(), ps[i].clear();
}
a[0].pb(t);
for (int i = k + 1; i < n; i++) {
a[0].pb(-(X[i] - X[i - 1]) / (2 * s));
a[0].pb(t);
}
a[1].pb(0);
for (int i = k - 1; ~i; i--) {
a[1].pb(-(X[i + 1] - X[i]) / (2 * s));
a[1].pb(t);
}
for (int i = 0; i < 2; i++) {
ps[i].pb(0);
for (auto x: a[i]) {
ps[i].pb(ps[i].back() + x);
}
}
flag = 0;
bool ans = check2();
reverse(all(ps[0]));
reverse(all(ps[1]));
flag = 1;
ans &= check2();
return ans;
}
void solve() {
if (n == 1) {
cout << 0;
return;
}
int L = 0, R = 1e9 + 1;
while (L + 1 < R) {
int m = (L + R) >> 1;
if (check(m)) {
R = m;
}
else {
L = m;
}
}
cout << R;
}
void read() {
cin >> n >> k >> t;
k--;
for (int i = 0; i < n; i++) {
cin >> X[i];
}
}
int main() {
ios::sync_with_stdio(0), cin.tie(0);
read();
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
