Submission #1273735

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273735		dung3683833	K blocks (IZhO14_blocks)	C++20	0 / 100	8 ms	13640 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int a[N];
struct T {
    int v;
    int v2;
    int l;
    bool kt;
} st[4*N];
int L[N];
int n, k;
int dp[105][N];
int lg[N];
inline void down(int id) {
    if (st[id].kt) {
        int& t = st[id].l;
        st[2*id].kt = 1;
        st[2*id].v = st[2*id].v2 + t;
        st[2*id].l = t;
        st[2*id+1].kt = 1;
        st[2*id+1].v = st[2*id+1].v2 + t;
        st[2*id+1].l = t;
        st[id].kt = 0;
    }
}
void upd1(int id, int l, int r, int u, int v, int k) {
    if (l > v || r < u) return;
    if (l >= u && r <= v) {
        st[id].kt = 1;
        st[id].v = st[id].v2 + k;
        st[id].l = k;
        return;
    }
    int mid = (l+r)/2;
    down(id);
    upd1(2*id, l, mid, u, v, k);
    upd1(2*id+1, mid+1, r, u, v, k);
    st[id].v2 = min(st[2*id].v2, st[2*id+1].v2);
    st[id].v = min(st[2*id].v, st[2*id+1].v);
}
void upd2(int id, int l, int r, int i, int v) {
    if (l > i || r < i) return;
    if (l == r) {
        st[id].v2 = v;
        st[id].v = v;
        return;
    }
    int mid = (l+r)/2;
    down(id);
    upd2(2*id, l, mid, i, v);
    upd2(2*id+1, mid+1, r, i, v);
    st[id].v2 = min(st[2*id].v2, st[2*id+1].v2);
    st[id].v = min(st[2*id].v, st[2*id+1].v);
}
int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u) return 1e18;
    if (l >= u && r <= v) return st[id].v;
    int mid = (l+r)/2;
    down(id);
    // int x = get(2*id, l, mid, u, v);
    // int y = get(2*id+1, mid+1, r, u, v);
    return min(get(2*id, l, mid, u, v), get(2*id+1, mid+1, r, u, v));
}
void prep() {
    stack<int> st;
    for (int i = 1; i <= n; i++) {
        while (st.size() && a[st.top()] <= a[i]) st.pop();
        if (st.size()) L[i] = st.top();
        else L[i] = -1;
        st.push(i);
    }
}
signed main() {
    // if (fopen("I.inp", "r")) {
    //     freopen("I.inp", "r", stdin);
    //     freopen("I.out", "w", stdout);
    // }
    cin.tie(0)->sync_with_stdio(false);
    for (int i = 2; i < N; i++) lg[i] = lg[i/2] + 1;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    prep();
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= n; j++) {
            dp[i][j] = 1e18;
        }
    }
    dp[0][0] = 0;
    for (int i = 1; i <= k; i++) {
        fill(st, st+4*N, T{0, 0, 0, 0});
        for (int j = 1; j <= n; j++) {
            upd1(1, 0, n, L[j]+1, j-1, a[j]);
            if (j >= i) {
                dp[i][j] = get(1, 0, n, i-1, j-1);
            }
            upd2(1, 0, n, j, dp[i-1][j]);
        }
    }
    cout << dp[k][n];
    return 0;
}

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