Submission #952544

#	Time	Username	Problem	Language	Result	Execution time	Memory
952544		ParsaGolestani	Sparklers (JOI17_sparklers)	C++17	0 / 100	1 ms	472 KiB

sparklers

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100'000;
const ll INF = 1'000'000'000;

ll n, k, t, s, x[N + 10];
stack<ll> a, b;

void readInput() {
    cin >> n >> k >> t;
    for (int i = 1; i <= n; i++)
        cin >> x[i];
}

stack<ll> empSt() {
    stack<ll> st;
    return st;
}

stack<ll> revSt(stack<ll> st) {
    stack<ll> res;
    while (st.size()) {
        res.push(-st.top());
        st.pop();
    }
    return res;
}

void calcA() {
    a = empSt();
    a.push(min(INF, t * s));
    for (int i = 2; i <= k; i++) {
        a.push(x[i - 1] - x[i]);
        a.push(min(INF, t * s));
    }
}

void calcB() {
    b = empSt();
    for (int i = n; i >= k + 1; i--) {
        b.push(min(INF, t * s));
        b.push(x[i - 1] - x[i]);
    }
}

void calcStack() {
    calcA();
    calcB();
}

pair<stack<ll>, stack<pair<ll, ll>>> compress(stack<ll> st) {
    stack<pair<ll, ll>> reverseRes, res;
    stack<ll> del;
    ll sum = 0, mn = 0;
    while (st.size()) {
        sum += st.top();
        mn = min(mn, sum);
        del.push(st.top());
        st.pop();
        if (sum >= 0) {
            reverseRes.push(make_pair(sum, mn));
            del = empSt();
            sum = mn = 0;
        }
    }
    while (del.size()) {
        st.push(del.top());
        del.pop();
    }
    while (reverseRes.size()) {
        res.push(reverseRes.top());
        reverseRes.pop();
    }
    return make_pair(st, res);
}

pair<ll, pair<stack<ll>, stack<ll>>> step(ll val, stack<ll> st1, stack<ll> st2) {
    auto p1 = compress(st1), p2 = compress(st2);
    stack<ll> resStack[2] = {p1.first, p2.first};
    stack<pair<ll, ll>> cmp[2] = {p1.second, p2.second};
    while (cmp[0].size() || cmp[1].size()) {
        bool ok = false;
        for (int id = 0; id < 2; id++)
            if (cmp[id].size() && val + cmp[id].top().second >= 0) {
                val += cmp[id].top().first;
                cmp[id].pop();
                ok = true;
            }
        if (!ok)
            return make_pair(-1ll, make_pair(a, b));
    }
    return make_pair(val, make_pair(resStack[0], resStack[1]));
}

ll calcSum() {
    return n * min(INF, t * s) - x[n];
}

bool check(ll mid) {
    s = mid;
    calcStack();
    auto x = step(0, a, b);
    if (x.first == -1)
        return false;
    return step(calcSum(), revSt(x.second.first), revSt(x.second.second)).first != -1;
}

void solve() {
    ll l = 0, r = INF;
    while (r - l > 1) {
        ll mid = (l + r) >> 1;
        if (check(mid + mid))
            r = mid;
        else
            l = mid;
    }
    cout << r << flush;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    solve();
    return 0;
}

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