// 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 = 2e5 + 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;
main_pa = max(main_pa, pa + 1);
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);
}
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, spA + Sz(A) + 1) - spA;
int indb = max_element(spB, 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 = 0, r = 1e9;
while(l < r) {
int mid = (l + r) >> 1;
if(okay(1ll * t * mid * 2)) r = mid;
else l = mid + 1;
}
cout<<l;
return 0;
}
Compilation message
sparklers.cpp: In function 'bool okay(ll)':
sparklers.cpp:86:9: warning: operation on 'spA[0]' may be undefined [-Wsequence-point]
86 | spA[0] = spA[0] = 0;
| ~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
328 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
460 KB |
Output is correct |
| 34 |
Correct |
1 ms |
336 KB |
Output is correct |
| 35 |
Correct |
1 ms |
336 KB |
Output is correct |
| 36 |
Correct |
1 ms |
340 KB |
Output is correct |
| 37 |
Correct |
1 ms |
340 KB |
Output is correct |
| 38 |
Correct |
1 ms |
468 KB |
Output is correct |
| 39 |
Correct |
1 ms |
340 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 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 |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
0 ms |
340 KB |
Output is correct |
| 13 |
Correct |
0 ms |
340 KB |
Output is correct |
| 14 |
Correct |
0 ms |
340 KB |
Output is correct |
| 15 |
Correct |
0 ms |
340 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
212 KB |
Output is correct |
| 18 |
Correct |
0 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
340 KB |
Output is correct |
| 21 |
Correct |
1 ms |
340 KB |
Output is correct |
| 22 |
Correct |
1 ms |
340 KB |
Output is correct |
| 23 |
Correct |
1 ms |
332 KB |
Output is correct |
| 24 |
Correct |
1 ms |
328 KB |
Output is correct |
| 25 |
Correct |
1 ms |
340 KB |
Output is correct |
| 26 |
Correct |
1 ms |
340 KB |
Output is correct |
| 27 |
Correct |
1 ms |
332 KB |
Output is correct |
| 28 |
Correct |
1 ms |
340 KB |
Output is correct |
| 29 |
Correct |
1 ms |
340 KB |
Output is correct |
| 30 |
Correct |
1 ms |
340 KB |
Output is correct |
| 31 |
Correct |
1 ms |
340 KB |
Output is correct |
| 32 |
Correct |
2 ms |
340 KB |
Output is correct |
| 33 |
Correct |
1 ms |
460 KB |
Output is correct |
| 34 |
Correct |
1 ms |
336 KB |
Output is correct |
| 35 |
Correct |
1 ms |
336 KB |
Output is correct |
| 36 |
Correct |
1 ms |
340 KB |
Output is correct |
| 37 |
Correct |
1 ms |
340 KB |
Output is correct |
| 38 |
Correct |
1 ms |
468 KB |
Output is correct |
| 39 |
Correct |
1 ms |
340 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
71 ms |
6832 KB |
Output is correct |
| 42 |
Correct |
4 ms |
604 KB |
Output is correct |
| 43 |
Correct |
19 ms |
2044 KB |
Output is correct |
| 44 |
Correct |
143 ms |
9628 KB |
Output is correct |
| 45 |
Correct |
122 ms |
9260 KB |
Output is correct |
| 46 |
Correct |
114 ms |
10532 KB |
Output is correct |
| 47 |
Correct |
111 ms |
10404 KB |
Output is correct |
| 48 |
Correct |
127 ms |
9204 KB |
Output is correct |
| 49 |
Correct |
152 ms |
9928 KB |
Output is correct |
| 50 |
Correct |
124 ms |
9900 KB |
Output is correct |
| 51 |
Correct |
115 ms |
10736 KB |
Output is correct |
| 52 |
Correct |
162 ms |
11004 KB |
Output is correct |
| 53 |
Correct |
151 ms |
9772 KB |
Output is correct |
| 54 |
Correct |
135 ms |
10888 KB |
Output is correct |
| 55 |
Correct |
116 ms |
9236 KB |
Output is correct |
| 56 |
Correct |
110 ms |
10664 KB |
Output is correct |
| 57 |
Correct |
128 ms |
9840 KB |
Output is correct |
| 58 |
Correct |
151 ms |
9572 KB |
Output is correct |
| 59 |
Correct |
111 ms |
7740 KB |
Output is correct |
| 60 |
Correct |
147 ms |
10976 KB |
Output is correct |
| 61 |
Correct |
177 ms |
10700 KB |
Output is correct |
| 62 |
Correct |
116 ms |
10624 KB |
Output is correct |
| 63 |
Correct |
138 ms |
10852 KB |
Output is correct |
| 64 |
Correct |
115 ms |
8924 KB |
Output is correct |
| 65 |
Correct |
131 ms |
9288 KB |
Output is correct |
| 66 |
Correct |
113 ms |
8988 KB |
Output is correct |
| 67 |
Correct |
114 ms |
9432 KB |
Output is correct |
| 68 |
Correct |
154 ms |
10988 KB |
Output is correct |
| 69 |
Correct |
141 ms |
10964 KB |
Output is correct |
