Submission #1312788

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312788		penguin133	K blocks (IZhO14_blocks)	C++17	0 / 100	0 ms	332 KiB

blocks

// Source: https://usaco.guide/general/io

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

struct node{
    ll s, e, m, val, lz;
    node *l, *r;
    node (int _s, int _e) {
        s = _s, e = _e, m = (s + e) >> 1;
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        }
        val = lz = 0;
    }

    void prop(){
        if (lz) {
            val += lz;
            if (s != e) l->lz += lz, r->lz += lz;
            lz = 0;
        }
    }

    void upd(int a, int b, ll c){
        if (a == s && b == e) lz += c;
        else {
            if (b <= m) l->upd(a, b, c);
            else if (a > m) r->upd(a, b, c);
            else l->upd(a, m, c), r->upd(m + 1, b, c);
            l->prop(), r->prop();
            val = min(l->val, r->val);
        }
    }

    ll qry(int a, int b){
        prop();
        if (a == s && b == e) return val;
        else if (b <= m) return l->qry(a, b);
        else if (a > m) return r->qry(a, b);
        else return min(l->qry(a, m), r->qry(m + 1, b));
    }
}*root;

ll a[100005], dp[105][100005];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    root = new node(1, n);
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) dp[0][i] = 1e14;
    for (int i = 1; i <= k; i++) dp[i][0] = 1e14;
    for (int i = 1; i <= 1; i++) {
        stack <int> s;
        s.push(0);
        for (int j = 1; j <= n; j++) {
            while (s.size() > 1) {
                int x = s.top(); 
                if (a[x] < a[j]) {
                    s.pop();
                    root->upd(s.top() + 1, x, a[j] - a[x]);
                }
                else break;
            }
            s.push(j);
            root->upd(j, j, dp[i - 1][j - 1] + a[j]);
            dp[i][j] = root->qry(1, j);
        }
    }
    for (int i = 2; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            root->upd(j, j, dp[i - 1][j - 1] - dp[i - 2][j - 1]);
            dp[i][j] = root->qry(1, j);
        }
    }
    cout << dp[k][n];
}

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