Submission #1101449

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101449		Anphat	K blocks (IZhO14_blocks)	C++14	53 / 100	1049 ms	8532 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define f first
#define s second
#define sz(a) (int)(a.size())
#define all(a) a.begin(), a.end()
#define uni(a) sort(all(a)), a.resize(unique(all(a)) - a.begin())

typedef pair <int, int> ii;

const int N = 1e5 + 5;

int n, k, a[N], ans, l[N], r[N];
stack <int> st;

struct segtree {
    int seg[N << 2], lazy[N << 2];

    void reset() {
        for (int i = 1; i <= (n << 2); i++) {
            lazy[i] = seg[i] = 1e9;
        }
    }

    void apply(int id, int val) {
        seg[id] = min(seg[id], val);
        lazy[id] = min(lazy[id], val);
    }

    void push(int id) {
        if (lazy[id] == 1e9) return;
        apply(id << 1, lazy[id]);
        apply(id << 1 | 1, lazy[id]);
        lazy[id] = 1e9;
    }

    void up(int l, int r, int id, int u, int v, int val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            apply(id, val);
            return;
        }
        push(id);
        int mid = (l + r) >> 1;
        up(l, mid, id << 1, u, v, val);
        up(mid + 1, r, id << 1 | 1, u, v, val);
        seg[id] = min(seg[id << 1], seg[id << 1 | 1]);
    }

    void up(int l, int r, int val) {
        up(0, n, 1, l, r, val);
    }

    int get(int l, int r, int id, int u, int v) {
        if (l > v || r < u) return 1e9;
        if (l >= u && r <= v) return seg[id];
        push(id);
        int mid = (l + r) >> 1;
        return min(get(l, mid, id << 1, u, v), get(mid + 1, r, id << 1 | 1, u, v));
    }

    int get(int l, int r) {
        return get(0, n, 1, l, r);
    }
} seg[2];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    //freopen("a.inp", "r", stdin);
    //freopen("a.out", "w", stdout);

    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    a[0] = a[n + 1] = 1e9;
    st.push(0);

    for (int i = 1; i <= n; i++) {
        while (a[st.top()] <= a[i]) st.pop();
        l[i] = st.top();
        st.push(i);
    }

    while (sz(st)) st.pop();
    st.push(n + 1);

    for (int i = n; i >= 1; i--) {
        while (a[st.top()] <= a[i]) st.pop();
        r[i] = st.top();
        st.push(i);
    }

    seg[0].reset(); seg[0].up(0, 0, 0);

    for (int j = 1; j <= k; j++) {
        seg[j & 1].reset();
        for (int i = 1; i <= n; i++) {
            seg[j & 1].up(i, r[i] - 1, seg[(j - 1) & 1].get(l[i], i - 1) + a[i]);
        }
    }

    cout << seg[k & 1].get(n, n) << '\n';

    return 0;
}

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