Submission #887464

#	Time	Username	Problem	Language	Result	Execution time	Memory
887464		Perl32	Stove (JOI18_stove)	C++14	100 / 100	871 ms	7728 KiB

stove

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INFL = (ll) 1e13 + 1e9;

struct SegTree {
    struct Node {
        ll v = INFL, c = 0;

        Node() = default;
        Node(ll v, ll c) : v(v), c(c) {}
    };

    vector<Node> t;
    int sz;

    SegTree(int n) {
        sz = 1;
        while (sz < n) sz <<= 1;
        t.resize(sz << 1);
    }

    Node merge(const Node &fir, const Node &sec) {
        if (fir.v < sec.v || (fir.v == sec.v && fir.c < sec.c)) {
            return fir;
        }
        return sec;
    }

    void upd(int i, Node v, int x, int lx, int rx) {
        if (lx + 1 == rx) {
            t[x] = v;
            return;
        }
        int m = (lx + rx) >> 1;
        if (i < m) {
            upd(i, v, x << 1, lx, m);
        } else {
            upd(i, v, x << 1 | 1, m, rx);
        }
        t[x] = merge(t[x << 1], t[x << 1 | 1]);
    }

    void upd(int i, Node v) {
        upd(i, v, 1, 0, sz);
    }

    Node get(int l, int r, int x, int lx, int rx) {
        if (rx <= l || r <= lx) {
            return Node();
        }
        if (l <= lx && rx <= r) {
            return t[x];
        }
        int m = (lx + rx) >> 1;
        return merge(get(l, r, x << 1, lx, m), get(l, r, x << 1 | 1, m, rx));
    }

    Node get(int l, int r) {
        return get(l, r, 1, 0, sz);
    }
};

signed main(int32_t argc, char *argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    a[0] = -1;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    SegTree st(n + 1);
    auto solve = [&](ll p) -> pair<ll, int> {
        vector<pair<ll, int>> dp(n + 1);
        dp[0] = {0, 0};
        st.upd(0, {0, 0});
        for (int i = 1; i <= n; ++i) {
            auto [v, c] = st.get(0, i);
            dp[i] = {dp[i - 1].first + 1 + p, dp[i - 1].second + 1};
            dp[i] = min(dp[i], {a[i] + 1 + v + p, c + 1});
            st.upd(i, {-a[i] + dp[i - 1].first, dp[i - 1].second});
        }
        return dp[n];
    };
    ll lx = -INFL, rx = INFL;
    while (lx + 1 < rx) {
        ll m = (lx + rx) >> 1;
        if (solve(m).second > k) {
            lx = m;
        } else {
            rx = m;
        }
    }
    auto [v, c] = solve(rx);
    cout << v - rx * k;
}

/*

 */

Compilation message (stderr)

stove.cpp: In lambda function:
stove.cpp:83:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   83 |             auto [v, c] = st.get(0, i);
      |                  ^
stove.cpp: In function 'int main(int32_t, char**)':
stove.cpp:99:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   99 |     auto [v, c] = solve(rx);
      |          ^

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