Submission #1208105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208105		gatapdev	K blocks (IZhO14_blocks)	C++20	0 / 100	0 ms	324 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;

// Segment tree supporting range-add and range-min queries
struct SegTree {
    int n;
    vector<ll> st, lazy;

    SegTree(int _n) : n(_n), st(4 * n, INF), lazy(4 * n, 0) {}

    void apply(int p, int l, int r, ll v) {
        st[p] += v;
        lazy[p] += v;
    }

    void push(int p, int l, int r) {
        if (lazy[p] != 0) {
            int m = (l + r) >> 1;
            apply(p << 1, l, m, lazy[p]);
            apply(p << 1 | 1, m + 1, r, lazy[p]);
            lazy[p] = 0;
        }
    }

    void pull(int p) {
        st[p] = min(st[p << 1], st[p << 1 | 1]);
    }

    void build(int p, int l, int r, const vector<ll>& base) {
        if (l == r) {
            st[p] = base[l];
            return;
        }
        int m = (l + r) >> 1;
        build(p << 1, l, m, base);
        build(p << 1 | 1, m + 1, r, base);
        pull(p);
    }

    void range_add(int p, int l, int r, int i, int j, ll v) {
        if (i > r || j < l) return;
        if (i <= l && r <= j) {
            apply(p, l, r, v);
            return;
        }
        push(p, l, r);
        int m = (l + r) >> 1;
        range_add(p << 1, l, m, i, j, v);
        range_add(p << 1 | 1, m + 1, r, i, j, v);
        pull(p);
    }

    ll range_min(int p, int l, int r, int i, int j) {
        if (i > r || j < l) return INF;
        if (i <= l && r <= j) return st[p];
        push(p, l, r);
        int m = (l + r) >> 1;
        return min(
            range_min(p << 1, l, m, i, j),
            range_min(p << 1 | 1, m + 1, r, i, j)
        );
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, K;
    cin >> n >> K;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // dp_prev[j]: best cost for up to j with k-1 segments
    // dp_cur[i]: best cost for up to i with k segments
    vector<ll> dp_prev(n + 1, INF), dp_cur(n + 1, INF);
    dp_prev[0] = 0;

    for (int k = 1; k <= K; k++) {
        // Build segment tree on dp_prev
        SegTree st(n + 1);
        st.build(1, 0, n, dp_prev);

        // Monotonic stack to track intervals of max values
        vector<int> stk, left(n + 1);
        stk.reserve(n);

        for (int i = 1; i <= n; i++) {
            int L = i;
            // Pop smaller or equal elements
            while (!stk.empty() && a[stk.back()] <= a[i]) {
                int t = stk.back();
                stk.pop_back();
                int lt = left[t];
                // For j in [lt-1, t-1], max increases from a[t] to a[i]
                st.range_add(1, 0, n, lt - 1, t - 1, a[i] - a[t]);
                L = lt;
            }
            stk.push_back(i);
            left[i] = L;

            // Query best dp for pos i with k segments
            dp_cur[i] = st.range_min(1, 0, n, 0, i - 1);
        }

        // Move to next layer
        dp_prev = dp_cur;
        fill(dp_cur.begin(), dp_cur.end(), INF);
    }

    cout << dp_prev[n] << '\n';
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47