This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, t;
cin >> n >> k >> t;
--k;
vector<int> x(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
}
auto Check = [&](long long s) {
auto Valid = [&](int from, int to) {
long long f = t * 1LL * (to - from);
if (f <= 5e8) {
f *= 2;
}
if (f <= 1e9) {
f *= s;
}
return f >= (x[to] - x[from]);
};
int L = k, R = k;
while (L > 0 || R < n - 1) {
if (L == 0) {
if (Valid(L, R + 1)) {
R += 1;
continue;
} else {
break;
}
}
if (R == n - 1) {
if (Valid(L - 1, R)) {
L -= 1;
continue;
} else {
break;
}
}
if (!Valid(L - 1, R) && !Valid(L, R + 1)) {
break;
}
if (!Valid(L - 1, R)) {
R += 1;
continue;
}
if (!Valid(L, R + 1)) {
L -= 1;
continue;
}
if (x[L] - x[L - 1] <= x[R + 1] - x[R]) {
L -= 1;
} else {
R += 1;
}
}
return (L == 0 && R == n - 1);
};
long long low = 0, high = 2e9, ans = -1;
while (low <= high) {
long long mid = low + high >> 1;
if (Check(mid)) {
ans = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
cout << ans << '\n';
return 0;
}
Compilation message (stderr)
sparklers.cpp: In function 'int main()':
sparklers.cpp:65:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | long long mid = low + high >> 1;
| ~~~~^~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |