// oooo
/*
har chi delet mikhad bebar ~
gitar o ba khodet nabar! ~
;Amoo_Hasan;
*/
#include<bits/stdc++.h>
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")
using namespace std;
typedef long long ll;
typedef long double ld;
#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl
constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;
int n, k;
ll x[N], spA[N], spB[N];
bool valid(vector<ll> vc1, vector<ll> vc2) {
int sa = Sz(vc1), sb = Sz(vc2);
if(vc1[sa - 1] + vc2[sb - 1] < 0) return 0;
int pa = 0, pb = 0, main_pa = 0;
while((pa < sa - 1) || (pb < sb - 1)) {
if(vc1[pa] + vc2[pb] < 0) return 0;
if(pa == sa - 1) {
pb++;
continue;
}
if(pb == sb - 1) {
pa++;
continue;
}
int fr = pa;
for(; main_pa < sa; main_pa++) {
if(vc1[main_pa] + vc2[pb] < 0) break;
if(vc1[main_pa] - vc1[pa] >= 0) {
pa = main_pa;
continue;
}
}
if(pa != fr) continue;
int main_pb = pb;
for(int i = main_pb + 1; i < sb; i++) {
if(vc2[i] + vc1[pa] < 0) break;
if(vc2[i] - vc2[pb] >= 0) {
main_pb = i;
break;
}
}
if(main_pb > pb) {
pb = main_pb;
continue;
}
return 0;
}
return 1;
}
bool okay(ll t) {
if(t > 1e9) return 1;
vector<ll> A = {t}, B;
for(int i = k + 1; i <= n; i++) {
A.push_back(-(x[i] - x[i - 1]));
A.push_back(t);
}
for(int i = k - 1; i > 0; i--) {
B.push_back(-(x[i + 1] - x[i]));
B.push_back(t);
}
/*
for(auto i : A) cout<<i <<' ';
cout<<endl;
for(auto i : B) cout<<i <<' ';
cout<<endl;*/
spA[0] = spA[0] = 0;
for(int i = 0; i < Sz(A); i++) spA[i + 1] = spA[i] + A[i];
for(int i = 0; i < Sz(B); i++) spB[i + 1] = spB[i] + B[i];
int inda = max_element(spA + 1, spA + Sz(A) + 1) - spA;
int indb = max_element(spB + 1, spB + Sz(B) + 1) - spB;
vector<ll> lA, rA, lB, rB;
for(int i = 0; i <= inda; i++) lA.push_back(spA[i]);
for(int i = inda; i <= Sz(A); i++) rA.push_back(spA[i]);
for(int i = 0; i <= indb; i++) lB.push_back(spB[i]);
for(int i = indb; i <= Sz(B); i++) rB.push_back(spB[i]);
reverse(All(rA)), reverse(All(rB));
return valid(lA, lB) && valid(rA, rB);
}
int main() {
ios :: sync_with_stdio(0), cin.tie(0);
ll t;
cin >>n >>k >>t;
for(int i = 1; i <= n; i++) cin >>x[i];
int l = -1, r = 1e9;
while(l + 1 < r) {
int mid = (l + r) >> 1;
if(okay(1ll * t * mid * 2)) r = mid;
else l = mid;
}
cout<<l + 1;
return 0;
}
Compilation message
sparklers.cpp: In function 'bool okay(ll)':
sparklers.cpp:90:9: warning: operation on 'spA[0]' may be undefined [-Wsequence-point]
90 | spA[0] = spA[0] = 0;
| ~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 21 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
340 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
1 ms |
340 KB |
Output is correct |
| 15 |
Correct |
1 ms |
340 KB |
Output is correct |
| 16 |
Correct |
1 ms |
340 KB |
Output is correct |
| 17 |
Correct |
1 ms |
340 KB |
Output is correct |
| 18 |
Correct |
0 ms |
340 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 21 |
Halted |
0 ms |
0 KB |
- |
