#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
ll t;
bool v[1001][1001];
ll pos[1001];
// ll dp[2][1000][1000];
// ll pos[1000];
vector<ll> all;
// bool go(int l, int r){
// if((pos[r]-pos[l]>2LL*t*(ll)(r-l))){
// return false;
// }
// if(v[l][r]){
// return false;
// }
// if(l==0 && r==n-1){
// return true;
// }
// v[l][r] = true;
// if(l>0 && go(l-1,r)){
// return true;
// }
// if(r<n-1 && go(l,r+1)){
// return true;
// }
// return false;
// }
int main(){
ll tt;
cin >> n >> k >> tt;
for(int i = 0; i<n; i++){
cin >> pos[i];
}
k--;
ll low = 0LL;
ll high = 1000000000LL;
while(low<high){
ll mid = (low+high)/2LL;
t = mid*tt;
vector<ll> ar[2];
for(int i = 0; i<2; i++){
ar[i].push_back(0);
}
for(int i = k+1; i<n; i++){
ar[0].push_back(ar[0][ar[0].size()-1] + 2LL * t - (pos[i]-pos[i-1]));
}
for(int i = k-1; i>=0; i--){
ar[1].push_back(ar[1][ar[1].size()-1] + 2LL * t - (pos[i+1] - pos[i]));
}
// if(mid==9LL){
// for(int i = 0; i<2; i++){
// for(int j = 0; j<ar[i].size(); j++){
// cout << ar[i][j] << " ";
// }
// cout << endl;
// }
// }
vector<pair<int, ll> > f[2];
vector<pair<int, ll> > b[2];
vector<ll> pre[2];
for(int i = 0; i<2; i++){
f[i].push_back(make_pair(0,0));
int sz = 1;
for(int j = 1; j<ar[i].size(); j++){
if(ar[i][j] > ar[i][f[i][sz-1].first]){
sz++;
f[i].push_back(make_pair(j,ar[i][j]));
}
}
for(int j = 0; j+1<sz; j++){
for(int a = f[i][j].first; a<f[i][j+1].first; a++){
f[i][j].second = min(f[i][j].second,ar[i][a]);
}
}
sz = 1;
b[i].push_back(make_pair(ar[i].size()-1,ar[i][ar[i].size()-1]));
for(int j = ar[i].size()-2; j>=0; j--){
if(ar[i][j] > ar[i][b[i][sz-1].first]){
sz++;
b[i].push_back(make_pair(j,ar[i][j]));
}
}
for(int j = 0; j+1<sz; j++){
for(int a = b[i][j+1].first+1; a<=b[i][j].first; a++){
b[i][j].second = min(b[i][j].second,ar[i][a]);
}
}
pre[i].resize(sz);
pre[i][sz-1] = b[i][sz-1].second;
for(int j = sz-2; j>=0; j--){
pre[i][j] = min(b[i][j].second,pre[i][j+1]);
}
}
bool ok = true;
int p1 = 0;
int p2 = 0;
while(p1+1<f[0].size() || p2+1<f[1].size()){
if(p1+1<f[0].size() && f[1][p2].first + f[0][p1].second >=0LL){
p1++;
}
else if(p2+1<f[1].size() && f[0][p1].first + f[1][p2].second >= 0LL){
p2++;
}
else{
ok = false;
break;
}
}
if(!ok){
low = mid+1LL;
continue;
}
p1 = 0;
p2 = 0;
// if(mid==9){
// cout << "TEMP " << endl;
// for(int i = 0; i<2; i++){
// for(int j = 0; j<pre[i].size(); j++){
// cout << pre[i][j] << " ";
// }
// cout << endl;
// }
// for(int i = 0; i<2; i++){
// for(int j = 0; j<pre[i].size(); j++){
// cout << b[i][j].first << "," << b[i][j].second << " ";
// }
// cout << endl;
// }
// }
while(p1+1<b[0].size() || p2+1<b[1].size()){
if(p1+1<b[0].size() && ar[1][b[1][p2].first] + b[0][p1].second >= 0LL && ar[0][b[0][p1+1].first] + pre[1][p2] >=0LL){
p1++;
}
else if(p2+1<b[1].size() && ar[0][b[0][p1].first] + b[1][p2].second >= 0LL && ar[1][b[1][p2+1].first] + pre[0][p1] >=0LL){
p2++;
}
else {
ok = false;
break;
}
}
// cout << mid << " " << ok << endl;
if(!ok){
low = mid+1LL;
}
else{
high = mid;
}
}
cout << low << endl;
}
Compilation message
sparklers.cpp: In function 'int main()':
sparklers.cpp:67:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 1; j<ar[i].size(); j++){
~^~~~~~~~~~~~~
sparklers.cpp:100:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p1+1<f[0].size() || p2+1<f[1].size()){
~~~~^~~~~~~~~~~~
sparklers.cpp:100:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p1+1<f[0].size() || p2+1<f[1].size()){
~~~~^~~~~~~~~~~~
sparklers.cpp:101:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p1+1<f[0].size() && f[1][p2].first + f[0][p1].second >=0LL){
~~~~^~~~~~~~~~~~
sparklers.cpp:104:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if(p2+1<f[1].size() && f[0][p1].first + f[1][p2].second >= 0LL){
~~~~^~~~~~~~~~~~
sparklers.cpp:133:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p1+1<b[0].size() || p2+1<b[1].size()){
~~~~^~~~~~~~~~~~
sparklers.cpp:133:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(p1+1<b[0].size() || p2+1<b[1].size()){
~~~~^~~~~~~~~~~~
sparklers.cpp:134:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(p1+1<b[0].size() && ar[1][b[1][p2].first] + b[0][p1].second >= 0LL && ar[0][b[0][p1+1].first] + pre[1][p2] >=0LL){
~~~~^~~~~~~~~~~~
sparklers.cpp:137:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
else if(p2+1<b[1].size() && ar[0][b[0][p1].first] + b[1][p2].second >= 0LL && ar[1][b[1][p2+1].first] + pre[0][p1] >=0LL){
~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
388 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
388 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
388 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
388 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
248 KB |
Output is correct |
| 2 |
Correct |
3 ms |
388 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
388 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
