#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define PB push_back
#define PPB pop_back
#define all(x) (x).begin(), (x).end()
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef long double ld;
const int MAXN = 47;
const int logo = 20;
const int off = 1 << logo;
const int trsz = off << 1;
const int mod = 1e9 + 7;
const ll inf = 1e18 + 7;
const ll INF = 1e18 + 7;
ll x[MAXN], n, k, t;
vll lef, rig;
vpll L, R;
bool okej(ll poc, vpll &vec){
for(auto &y : vec){
if(poc + y.Y < 0) return 0;
poc += y.X;
}
return poc >= 0;
}
ll balance = 0;
struct Stack {
vector<ll> v;
vector<ll> pre;
int cur_idx = 0;
int max_idx = 0;
ll sum = 0;
set<pair<ll, ll> > s;
void create(vector<ll> _v) {
cur_idx = 0;
max_idx = 0;
v = _v;
sum = 0;
pre.resize(v.size());
pre[0] = v[0];
for (int i = 1; i < (int)v.size(); ++i) pre[i] = v[i] + pre[i - 1];
s.insert({-1e17, -1});
}
void extend() {
while (max_idx < (int)v.size() && balance + pre[max_idx] - sum >= 0) {
s.insert({pre[max_idx], max_idx});
++max_idx;
}
}
void makni() {
int idx = (*s.rbegin()).second;
while (cur_idx <= idx) {
assert(s.find({pre[cur_idx], cur_idx}) != s.end());
s.erase(s.find({pre[cur_idx], cur_idx}));
balance += v[cur_idx];
sum += v[cur_idx];
++cur_idx;
}
}
ll delta() {
return (*s.rbegin()).first - sum;
}
} A, B;
bool resi(vector<ll> a, vector<ll> b) {
A.create(a);
B.create(b);
A.extend();
B.extend();
while (balance + max(A.delta(), B.delta()) >= 0) {
if (A.delta() > B.delta()) A.makni();
else B.makni();
A.extend();
B.extend();
}
return (A.cur_idx == (int)a.size() && B.cur_idx == (int)b.size());
}
bool check(ll mid){
lef.clear();
rig.clear();
L.clear();
R.clear();
for(int i=k; i<n; i++) rig.PB((ll)2 * mid * t - (ll)(x[i + 1] - (ll)x[i]) / 2);
for(int i=1; i<k; i++) lef.PB((ll)2 * mid * t - (ll)(x[i + 1] - (ll)x[i]) / 2);
reverse(all(rig));
balance = 0;
return resi(lef, rig);
}
void solve(){
cin >> n >> k >> t;
for(int i=1; i<=n; i++) cin >> x[i], x[i] *= 2;
int lo = 1, hi = ((1e9 + 1) / t) + 1, ret = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(check(mid)) hi = mid - 1, ret = mid;
else lo = mid + 1;
}
cout << ret << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
//cin >> t;
while(tt--) solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
