// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 1e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
ll n, k, t;
multiset <ll> avl, avr;
ll x[maxn5], cur[maxn5];
ll val[maxn5], w[maxn5];
inline bool check(ll s){
for(int i = k - 1; i >= 0; i--){
val[i] = 2 * s * t - x[i + 1] + x[i];
cur[i] = val[i] + cur[i + 1];
w[i] = x[i + 1] - x[i] - cur[i + 1];
}
for(int i = k + 1; i < n; i++){
val[i] = 2 * s * t - x[i] + x[i - 1];
cur[i] = val[i] + cur[i - 1];
w[i] = x[i] - x[i - 1] - cur[i - 1];
}
cur[k] = 0;
int l = k - 1, r = k + 1, lq = k - 1, rq = k + 1;
ll lim = 2 * t * s;
ll lqsum = 0, rqsum = 0;
ll exl = lim, exr = lim;
while(l >= 0 || r < n){
bool re = false;
//cout << "* " << s << ' ' << l << ' ' << r << ' ' << exl << ' ' << exr << ' ' << val[r] << ' ' << w[l] << '\n';
while(lq >= 0 && w[lq] <= exr){
lqsum += val[lq];
lq--;
if(lqsum >= 0){
exl += lqsum;
lqsum = 0;
l = lq;
re = true;
}
}
while(rq < n && w[rq] <= exl){
rqsum += val[rq];
rq++;
if(rqsum >= 0){
exr += rqsum;
rqsum = 0;
r = rq;
re = true;
}
}
//cout << "ok " << re << '\n';
if(!re){
avl.clear();
avr.clear();
for(int i = 0; i <= l; i++)
avl.insert(-w[i]);
for(int i = r; i < n; i++)
avr.insert(-w[i]);
while(l >= 0 || r < n){
bool re = false;
while(l >= 0 && w[l] <= exr && (r == n || exl + val[l] >= -1 * (*avr.begin()))){
exl += val[l];
avl.erase(avl.find(-w[l]));
l--;
re = true;
}
while(r < n && w[r] <= exl && (l < 0 || exr + val[r] >= -1 * (*avl.begin()))){
exr += val[r];
avr.erase(avr.find(-w[r]));
r++;
re = true;
}
if(!re)
return false;
}
break;
}
}
return true;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin >> n >> k >> t;
k--;
for(int i = 0; i < n; i++)
cin >> x[i];
ll lo = -1, hi = 1e9 + 1;
while(hi - lo > 1){
ll mid = (lo + hi) >> 1;
if(check(mid))
hi = mid;
else
lo = mid;
}
cout << hi << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
324 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |