#if 1
#ifndef ONLINE_JUDGE
#define _GLIBCXX_DEBUG 1
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
#include <bits/stdc++.h>
using namespace std;
#if 0
#include <bits/extc++.h>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
tree_order_statistics_node_update>;
#endif
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
typedef string str;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<typename T, typename U> T &ctmax(T &x, const U &y){ return x = max<T>(x, y); }
template<typename T, typename U> T &ctmin(T &x, const U &y){ return x = min<T>(x, y); }
mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
#define ts to_string
str ts(char c) { return str(1,c); }
str ts(bool b) { return b ? "true" : "false"; }
str ts(const char* s) { return (str)s; }
str ts(str s) { return s; }
template<class A> str ts(complex<A> c) { stringstream ss; ss << c; return ss.str(); }
str ts(vector<bool> v) { str res = "{"; F0R(i,sz(v)) res += char('0'+v[i]); res += "}"; return res; }
template<size_t SZ> str ts(bitset<SZ> b) { str res = ""; F0R(i,SZ) res += char('0'+b[i]); return res; }
template<class A, class B> str ts(pair<A,B> p);
template<class T> str ts(T v) { bool fst = 1; str res = "{"; for (const auto& x: v) {if (!fst) res += ", "; fst = 0; res += ts(x);} res += "}"; return res;}
template<class A, class B> str ts(pair<A,B> p) {return "("+ts(p.first)+", "+ts(p.second)+")"; }
template<class A> void pr(A x) { cout << ts(x); }
template<class H, class... T> void pr(const H& h, const T&... t) { pr(h); pr(t...); }
void ps() { pr("\n"); }
template<class H, class... T> void ps(const H& h, const T&... t) { pr(h); if (sizeof...(t)) pr(" "); ps(t...); }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {cerr << ts(h); if (sizeof...(t)) cerr << ", "; DBG(t...); }
int myrand(int l, int r) { return uniform_int_distribution(l, r)(rng); }
#endif
bool go(const vector<ll> &pl, const vector<ll> &pr) {
vector<long long> left_max_pref(sz(pl));
vector<long long> right_max_pref(sz(pr));
for (int i = 0; i < sz(pl); i++) {
left_max_pref[i] = i==0 ? pl[i] : max(left_max_pref[i-1], pl[i]);
}
for (int i = 0; i < sz(pr); i++) {
right_max_pref[i] = i==0 ? pr[i] : max(right_max_pref[i-1], pr[i]);
}
vector< int > minimums_left;
vector< int > minimums_right;
for (int i = 0; i < sz(pl); i++) {
if (minimums_left.empty() || pl[minimums_left.back()] >= pl[i]) {
minimums_left.push_back(i);
}
}
for (int i = 0; i < sz(pr); i++) {
if (minimums_right.empty() || pr[minimums_right.back()] >= pr[i]) {
minimums_right.push_back(i);
}
}
int cur_left = 0, cur_right = 0;
while (cur_left+1 != sz(minimums_left) || cur_right+1 != sz(minimums_right)) {
// dbg(cur_left, cur_right, minimums_left, minimums_right, pl[minimums_left[cur_left]], pr[minimums_right[cur_right]]);
bool moved = false;
if (cur_left+1 != sz(minimums_left) && pr[minimums_right[cur_right]] + left_max_pref[minimums_left[cur_left+1]] <= 0) {
cur_left++;
moved = true;
}
if (cur_right+1 != sz(minimums_right) && pr[minimums_left[cur_left]] + right_max_pref[minimums_right[cur_right+1]] <= 0) {
cur_right++;
moved = true;
}
if (!moved) return false;
}
return true;
}
bool check(long long speed, vector<ll> left, vector<ll> right, int t) {
if (t * 1ll * speed * 2 >= 1000000000) return true;
for (auto &x : left) x -= (t * 1ll * speed * 2);
for (auto &x : right) x -= (t * 1ll * speed * 2);
// dbg(left, right);
vector<long long> pl(sz(left)+1), pr(sz(right)+1);
partial_sum(all(left), pl.begin()+1);
partial_sum(all(right), pr.begin()+1);
// dbg(pl, pr);
bool ok = go(pl, pr);
reverse(all(pl));
reverse(all(pr));
ok = ok && go(pl, pr);
return ok;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, t;
cin >> n >> k >> t; k--;
vector<ll> left, right;
vi a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
if (i < k) {
left.push_back(a[i+1] - a[i]);
}
else if (i > k) {
right.push_back(a[i] - a[i-1]);
}
}
reverse(all(left));
// bool o =check(6, left, right, t);
// dbg(o);
long long st = 1, ed = 1000000000;
while (st < ed) {
// dbg(st,ed);
long long md = (st+ed)/2;
if (check(md, left, right, t)) ed = md;
else st=md+1;
}
cout << st << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
