Submission #1208123

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208123		gatapdev	K개의 묶음 (IZhO14_blocks)	C++20	53 / 100	1095 ms	7708 KiB

blocks

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

// Bottom-up segment tree supporting range-add and range-min
struct SegTree {
    int n;
    vector<ll> tree, lazy;
    SegTree(int _n) : n(_n), tree(2*n, INF), lazy(n, 0) {}

    // build from base array of size n+1 (0..n)
    void build(const vector<ll>& base) {
        for (int i = 0; i <= n; i++) tree[i + n] = base[i];
        for (int i = n - 1; i >= 1; i--) tree[i] = min(tree[i<<1], tree[i<<1|1]);
    }

    // apply at position p
    void apply(int p, ll v) {
        tree[p] += v;
        if (p < n) lazy[p] += v;
    }

    // push from p
    void push(int p) {
        int h = __builtin_ctz(p);
        for (int s = h; s > 0; s--) {
            int i = p >> s;
            if (lazy[i]) {
                apply(i<<1, lazy[i]);
                apply(i<<1|1, lazy[i]);
                lazy[i] = 0;
            }
        }
    }

    // pull at p
    void pull(int p) {
        while (p > 1) {
            p >>= 1;
            tree[p] = min(tree[p<<1], tree[p<<1|1]) + lazy[p];
        }
    }

    // range add [l, r]
    void range_add(int l, int r, ll v) {
        l += n; r += n;
        int l0 = l, r0 = r;
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l&1) apply(l++, v);
            if (!(r&1)) apply(r--, v);
        }
        pull(l0);
        pull(r0);
    }

    ll range_min(int l, int r) {
        l += n; r += n;
        push(l); push(r);
        ll res = INF;
        for (; l <= r; l >>= 1, r >>= 1) {
            if (l&1) res = min(res, tree[l++]);
            if (!(r&1)) res = min(res, tree[r--]);
        }
        return res;
    }
};

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];

    vector<ll> dp_prev(n+1, INF), dp_cur(n+1, INF);
    dp_prev[0] = 0;
    // base k=1
    for (int i = 1; i <= n; i++) dp_prev[i] = max(dp_prev[i-1], a[i]);

    SegTree st(n+1);
    for (int k = 2; k <= K; k++) {
        st = SegTree(n+1);
        st.build(dp_prev);
        vector<int> stk, left(n+1);
        for (int i = k; i <= n; i++) dp_cur[i] = INF;
        for (int i = k; i <= n; i++) {
            int L = i;
            while (!stk.empty() && a[stk.back()] <= a[i]) {
                int t = stk.back(); stk.pop_back();
                int lt = left[t];
                st.range_add(lt-1, t-1, -a[t]);
                L = lt;
            }
            stk.push_back(i);
            left[i] = L;
            st.range_add(L-1, i-1, a[i]);
            dp_cur[i] = st.range_min(k-1, i-1);
        }
        dp_prev.swap(dp_cur);
    }
    cout << dp_prev[n] << "\n";
    return 0;
}

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