Submission #1217309

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217309		lmaobruh	K blocks (IZhO14_blocks)	C++20	53 / 100	1086 ms	4096 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL<<60);

struct SegTree {
    int n;
    vector<ll> st, lz;
    SegTree(int _n): n(_n), st(4*n, INF), lz(4*n, 0) {}

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

    void push(int p) {
        if (lz[p]) {
            apply(p<<1, lz[p]);
            apply(p<<1|1, lz[p]);
            lz[p] = 0;
        }
    }

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

    void update_range(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, v);
            return;
        }
        push(p);
        int m=(l+r)>>1;
        update_range(p<<1, l, m, i, j, v);
        update_range(p<<1|1, m+1, r, i, j, v);
        pull(p);
    }
    void update_point(int p, int l, int r, int idx, ll value) {
        if (l==r) {
            st[p] = value;
            lz[p] = 0;
            return;
        }
        push(p);
        int m=(l+r)>>1;
        if (idx<=m) update_point(p<<1, l, m, idx, value);
        else          update_point(p<<1|1, m+1, r, idx, value);
        pull(p);
    }

    ll query_min() {
        return st[1];
    }
};

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

    int N, K;
    cin >> N >> K;
    vector<int> 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;

    for(int k=1;k<=K;k++){
        SegTree st(N);
        vector<pair<int,int>> stk;
        stk.reserve(N);
        st.update_point(1, 0, N-1, 0, dp_prev[0]);
        stk.emplace_back(A[1], 0);
        st.update_range(1, 0, N-1, 0, 0, A[1]);

        for(int i=1;i<=N;i++){
            if (i>1) {
                st.update_point(1, 0, N-1, i-1, dp_prev[i-1]);
                int L = i-1;
                while(!stk.empty() && stk.back().first <= A[i]){
                    auto [v, lft] = stk.back();
                    stk.pop_back();
                    st.update_range(1, 0, N-1, lft, L-1, -v);
                    L = lft;
                }
                stk.emplace_back(A[i], L);
                st.update_range(1, 0, N-1, L, i-1, A[i]);
            }
            dp_cur[i] = st.query_min();
        }
        dp_prev = dp_cur;
        fill(dp_cur.begin(), dp_cur.end(), INF);
    }

    cout << dp_prev[N] << "\n";
    return 0;
}

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