#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve(int n, int k, ll t, vector<int> x) {
if(k<0 || k>=n) return false;
vector<ll> dp(n);
dp[0] = 0;
for(int i=1; i<k; ++i) {
dp[i] = max((ll)0, dp[i-1] + (x[i] - x[i-1])/2 - t);
}
dp[n-1] = 0;
for(int i=n-2; i>k; --i) {
dp[i] = max((ll)0, dp[i+1] + (x[i+1] - x[i])/2 - t);
}
if(k < n-1 && dp[k+1] + (x[k+1] - x[k]) / 2 > t) {
return false;
}
if(k == 0) return true;
ll T = (n - 1 - k) * t;
ll p1 = x[n-1] - T;
ll p2 = x[k-1] - min(dp[k-1], T) + max(0LL, T - dp[k-1]);
return (p1 - p2) / 2 <= t;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, k;
ll t;
cin>>n>>k>>t;
k--;
t *= 2;
vector<int> x(n);
for(int i=0; i<n; ++i) {
cin>>x[i];
x[i] *= 2;
}
auto xr = x;
reverse(xr.begin(), xr.end());
for(auto& i: xr) {
i = x[n-1] - i;
}
int lo = 0, hi = 1e9 / t + 1;
while(lo<=hi) {
int mid = (lo+hi)/2;
//if(solve(n, k, t*mid, x) || solve(n, n-k-1, t*mid, xr) || solve(n, k-1, t*mid, x) || solve(n, n-(k+1)-1, t*mid, xr)) {
if(solve(n, k, t*mid, x) || solve(n, n-k-1, t*mid, xr)) {
hi = mid-1;
}
else {
lo = mid+1;
}
}
cout<<hi+1<<'\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
