#include <bits/stdc++.h>
#define fi first
#define se second
#define fin(s) freopen( s, "r", stdin );
#define fout(s) freopen( s, "w", stdout );
const long long N = 100100;
const long long Q = N * 30;
const long long mod = 1e9 + 7;
const long long MAGIC = 30;
using namespace std;
int n;
int k;
int t;
int a[N];
bool can(long long s)
{
s *= t;
vector < long long > l, r;
for(int i = 1; i < k; i++){
l.push_back(a[k] - a[i]);
}
for(int i = n; i > k; i--){
r.push_back(a[i] - a[k]);
}
/*for(int x: l){
cout << x << " ";
} cout << "\n";
for(int i = 0; i + 1 < l.size(); i++){
cout << l[i] - l[i + 1] << " ";
} cout << "\n";
for(int x: r){
cout << x << " ";
} cout << "\n";
for(int i = 0; i + 1 < r.size(); i++){
cout << r[i] - r[i + 1] << " ";
} cout << "\n";*/
long long dl = 0, dr = 0;
while(!l.empty() || !r.empty()){
if(!l.empty() && s * 2 >= (l.back() - dl)){
long long f = l.back() - dl;
if(s >= f){
dr += (s - f) * 2 + f;
dl += f;
}
else{
dr += (s + s - f);
dl += (f - s) * 2 + (s + s - f);
}
l.pop_back();
}
else if(!r.empty() && s * 2 >= (r.back() - dr)){
long long f = r.back() - dr;
if(s >= f){
dl += (s - f) * 2 + f;
dr += f;
}
else{
dl += (s + s - f);
dr += (f - s) * 2 + (s + s - f);
}
r.pop_back();
}
else{
return false;
}
while(!l.empty() && l.back() - dl <= 0){
l.pop_back();
}
while(!r.empty() && r.back() - dr <= 0){
r.pop_back();
}
}
/*for(int i = 0; i + 1 < r.size(); i++){
cout << r[i] - r[i + 1] << " ";
}*/
return true;
}
void solve()
{
cin >> n >> k >> t;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
long long l = 1, r = 1e9 + 1;
//cout << can(6) << endl;
//return;
while(l < r){
long long m = (l + r) / 2;
if(can(m)){
r = m;
}
else{
l = m + 1;
}
}
cout << l << "\n";
}
bool mtest = false; int main()
{
//fin("input.txt");
//fout("output.txt");
//fin("island.in");
//fout("island.out");
ios_base::sync_with_stdio(0);
int TE = 1;
if(mtest)
cin >> TE;
while(TE--)
solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
