#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define Pii pair< pii , pii >
#define int long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 6e5 + 10 , sq = 3 , maxq = 1e7 + 1 , inf = 1e18 + 10 , mod= 998244353 ,lg = 20 ;
int n ,t , k;
vector <int> a , b ;
int x[maxn] ;
int pa[maxn] , pb[maxn] , ma[maxn] , mb[maxn] ;
int sl(){
vector <int> va , vb ;
va.pb(0);vb.pb(0);
for(int i = 1; i < a.size() ; i++){
pa[i] = pa[i-1] + a[i] ;
if(pa[i] > pa[va.back()]){
ma[va.size()-1] = 0 ;
for(int j = va.back() + 1 ; j < i ; j++){
ma[va.size()-1] = min(ma[va.size()-1] , pa[j] - pa[va.back()]) ;
}
va.pb(i) ;
}
}
for(int i = 1; i < b.size() ; i++){
pb[i] = pb[i-1] + b[i] ;
if(pb[i] > pb[vb.back()]){
mb[vb.size()-1] = 0 ;
for(int j = vb.back() + 1 ; j < i ; j++){
mb[vb.size()-1] = min(mb[vb.size()-1] , pb[j] - pb[vb.back()]) ;
}
vb.pb(i) ;
}
}
int id1 = 0 , id2 =0 , val = 0 ;
while(1){
if(id1!=va.size()-1 && pa[va[id1]]+pb[vb[id2]]+ma[id1] >=0 ){
id1++;
continue ;
}
if(id2!=vb.size()-1 && pa[va[id1]]+pb[vb[id2]]+mb[id2] >= 0){
id2++;
continue ;
}
break ;
}
if(id1!=va.size()-1 || id2 != vb.size()-1){
return 0 ;
}
id1 = va[id1] + 1 ;
id2 = vb[id2] + 1 ;
vector<int> vec , vec2 ;
for(int i =id1 ; i < a.size() ; i++)vec.pb(a[i]) ;
for(int i =id2 ; i < b.size() ; i++)vec.pb(b[i]) ;
for(int i =id2 ; i < b.size() ; i++)vec2.pb(b[i]) ;
for(int i =id1 ; i < a.size() ; i++)vec2.pb(a[i]) ;
int sm = pa[id1-1] + pb[id2-1] ;
bool ok1 =1 ,ok2 =1 ;
for(int i =0 ; i < vec.size() ;i++){
if(sm > 1e9)break ;
sm += vec[i] ;
if(sm < 0)ok1 =0 ;
}
sm =pa[id1-1] +pb[id2-1] ;
for(int i= 0 ; i < vec2.size() ; i++){
if(sm > 1e9)break ;
sm+=vec2[i] ;
if(sm < 0)ok2 =0 ;
}
return ok1|ok2 ;
}
bool ch(int z){
a.clear();b.clear();
a.pb(0);
b.pb(0) ;
a.pb(t*2*z);
for(int i = k+1; i <= n ; i++){
a.pb(-(x[i] - x[i-1]));
a.pb(t*2*z) ;
}
for(int i = k-1 ; i >= 1; i--){
b.pb(-(x[i+1] - x[i]));
b.pb(t*2*z) ;
}
return sl() ;
}
signed main() {
ios::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
cin >> n >> k >> t ;
for(int i = 1; i <= n ; i++){
cin >> x[i] ;
}
int l = 0 , r = 5e8 + 1 ;
while(r-l>1){
int mid = (l+r)/2 ;
if(ch(mid) == 1)r= mid ;
else l = mid ;
}
cout << r << "\n";
}
/*
*/
Compilation message
sparklers.cpp: In function 'long long int sl()':
sparklers.cpp:21:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i = 1; i < a.size() ; i++){
| ~~^~~~~~~~~~
sparklers.cpp:31:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 1; i < b.size() ; i++){
| ~~^~~~~~~~~~
sparklers.cpp:43:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | if(id1!=va.size()-1 && pa[va[id1]]+pb[vb[id2]]+ma[id1] >=0 ){
| ~~~^~~~~~~~~~~~~
sparklers.cpp:47:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(id2!=vb.size()-1 && pa[va[id1]]+pb[vb[id2]]+mb[id2] >= 0){
| ~~~^~~~~~~~~~~~~
sparklers.cpp:53:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if(id1!=va.size()-1 || id2 != vb.size()-1){
| ~~~^~~~~~~~~~~~~
sparklers.cpp:53:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if(id1!=va.size()-1 || id2 != vb.size()-1){
| ~~~~^~~~~~~~~~~~~~
sparklers.cpp:59:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for(int i =id1 ; i < a.size() ; i++)vec.pb(a[i]) ;
| ~~^~~~~~~~~~
sparklers.cpp:60:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i =id2 ; i < b.size() ; i++)vec.pb(b[i]) ;
| ~~^~~~~~~~~~
sparklers.cpp:61:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i =id2 ; i < b.size() ; i++)vec2.pb(b[i]) ;
| ~~^~~~~~~~~~
sparklers.cpp:62:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i =id1 ; i < a.size() ; i++)vec2.pb(a[i]) ;
| ~~^~~~~~~~~~
sparklers.cpp:65:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i =0 ; i < vec.size() ;i++){
| ~~^~~~~~~~~~~~
sparklers.cpp:71:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | for(int i= 0 ; i < vec2.size() ; i++){
| ~~^~~~~~~~~~~~~
sparklers.cpp:41:26: warning: unused variable 'val' [-Wunused-variable]
41 | int id1 = 0 , id2 =0 , val = 0 ;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4584 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4584 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4584 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4696 KB |
Output is correct |
| 7 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 12 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 13 |
Halted |
0 ms |
0 KB |
- |
