Submission #889613

#	Time	Username	Problem	Language	Result	Execution time	Memory
889613		dwuy	K blocks (IZhO14_blocks)	C++14	53 / 100	1071 ms	6992 KiB

blocks

/// dwuy: _,\,,,_\,__,\,,_
#include <bits/stdc++.h>

#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL)
#define file(a) freopen(a".inp","r",stdin); freopen(a".out", "w",stdout)
#define fi first
#define se second
#define endl "\n"
#define len(s) int32_t(s.length())
#define MASK(k)(1LL<<(k))
#define TASK ""

using namespace std;

typedef tuple<int, int, int> tpiii;
typedef pair<double, double> pdd;
typedef pair<int, int> pii;
typedef long long ll;

const long long OO = 1e18;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MX = 100005;

struct Node{
    int mn, lz, f;
    Node(){
        this->mn = INF;
        this->lz = 0;
        this->f = INF;
    }
};

struct SMT{
    int n;
    vector<Node> tree;

    SMT(int n=0){
        this->n = n;
        this->tree.assign(n<<2|1, Node());
    }

    void down(int id){
        if(tree[id].lz == 0) return;
        int ID = id<<1;
        int &val = tree[id].lz;
        tree[ID].lz = val;
        tree[ID].mn = tree[ID].f + val;
        tree[ID|1].lz = val;
        tree[ID|1].mn = tree[ID|1].f + val;
        val = 0;
    }

    void pointUpd(int pos, int val){
        int id = 1;
        for(int lo=1, hi=n; lo<hi;){
            down(id);
            int mid = (lo+hi)>>1;
            if(pos<=mid) hi = mid, id = id<<1;
            else id = id<<1|1, lo = mid + 1;
        }
        tree[id].f = tree[id].mn = val;
        for(id>>=1; id; id>>=1){
            tree[id].f = min(tree[id<<1].f, tree[id<<1|1].f);
            tree[id].mn = min(tree[id<<1].mn, tree[id<<1|1].mn);
        }
    }

    void rangeUpd(int l, int r, int id, const int &u, const int &v, int val){
        if(l>v || r<u) return;
        if(l>=u && r<=v){
            tree[id].mn = val + tree[id].f;
            tree[id].lz = val;
            return;
        }
        down(id);
        int mid = (l+r)>>1;
        int ID = id<<1;
        rangeUpd(l, mid, ID, u, v, val);
        rangeUpd(mid+1, r, ID|1, u, v, val);
        tree[id].mn = min(tree[ID].mn, tree[ID|1].mn);
    }

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

    int get(){
        return tree[1].mn;
    }
};

int n, k;
int a[MX];
int cur[MX];
int pre[MX];

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

void solve(){
    for(int i=1, mx=0; i<=n; i++){
        mx = max(mx, a[i]);
        pre[i] = mx;
    }
    for(int j=2; j<=k; j++){
        stack<int> st;
        SMT smt(n);
        a[j-1] = INF;
        st.push(j-1);
        for(int i=j; i<=n; i++){
            while(a[st.top()] <= a[i]) st.pop();
            smt.pointUpd(i, pre[i-1]);
            smt.rangeUpd(st.top()+1, i, a[i]);
            cur[i] = smt.get();
            st.push(i);
        }
        for(int i=j; i<=n; i++) pre[i] = cur[i];
    }
    cout << pre[n];
}

int32_t main(){
    fastIO;
    //file(TASK);

    nhap();
    solve();

    return 0;
}

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