Submission #702114

#	Time	Username	Problem	Language	Result	Execution time	Memory
702114		GrandTiger1729	K blocks (IZhO14_blocks)	C++17	0 / 100	0 ms	212 KiB

blocks

#include <iostream>
#include <deque>
#include <set>
#include <cassert>
using namespace std;

const int INF = 1e9;
struct segTree{
    int l, r, mid;
    int val = 0, lz = 0;
    segTree *lc, *rc;
    segTree() = default;
    segTree(int _l, int _r): l(_l), r(_r){
        mid = (l + r) / 2;
        if (l == r - 1) return;
        lc = new segTree(l, mid);
        rc = new segTree(mid, r);
    }
    int real_val(){
        return val + lz;
    }
    void push(){
        if (lz > 0){
            lc->lz += lz;
            rc->lz += lz;
            lz = 0;
        }
    }
    void pull(){
        val = min(lc->real_val(), rc->real_val());
    }
    void update(int ll, int rr, int u){
        if (ll <= l && rr >= r){
            lz = u;
            return;
        }
        push();
        if (ll < mid)
            lc->update(ll, rr, u);
        if (mid < rr)
            rc->update(ll, rr, u);
        pull();
    }
    int query(int ll, int rr){
        if (ll <= l && rr >= r){
            return real_val();
        }
        push();
        int ret = INF;
        if (ll < mid)
            ret = min(ret, lc->query(ll, rr));
        if (mid < rr)
            ret = min(ret, rc->query(ll, rr));
        pull();
        return ret;
    }
};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int n, m; cin >> n >> m;
    int a[n + 1]{};
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int dp[n + 1][m + 1]{};
    fill_n(&dp[0][0], sizeof(dp) / sizeof(int), INF);
    deque<int> dq;
    a[0] = INF;
    dp[0][0] = 0;
    dq.push_back(0);
    segTree st[m];
    for (int i = 0; i < m; i++){
        st[i] = segTree(0, n + 1);
        if (i > 0) st[i].update(0, 1, INF);
    }
    for (int i = 1; i <= n; i++){
        // for (int j = 1; j <= m; j++){
        //     int cur = a[i];
        //     for (int k = i - 1; k >= 0; k--){
        //         dp[i][j] = min(dp[i][j], dp[k][j - 1] + cur);
        //         cur = max(cur, a[k]);
        //     }
        // }
        while (dq.size() && a[dq.back()] < a[i]){
            int k = dq.back();
            dq.pop_back();
            for (int j = 1; j <= m; j++){
                // assert(st[j - 1].find(dp[dq.back()][j - 1] + a[k]) != st[j - 1].end());
                // st[j - 1].erase(st[j - 1].find(dp[dq.back()][j - 1] + a[k]));
                st[j - 1].update(dq.back() + 1, k, a[i] - a[k]);
            }
        }
        for (int j = 1; j <= m; j++){
            dp[i][j] = st[j - 1].query(0, i) + a[i];
            st[j - 1].update(i, i + 1, dp[i][j - 1]);
        }
        dq.push_back(i);
    }
    cout << dp[n][m] << '\n';
    return 0;
}

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