Submission #385440

#	Time	Username	Problem	Language	Result	Execution time	Memory
385440		ffao	Sparklers (JOI17_sparklers)	C++17	100 / 100	371 ms	5964 KiB

sparklers

#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) && pl[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 = 0, 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;
}

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50