제출 #1306138

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306138		Sofiatpc	K개의 묶음 (IZhO14_blocks)	C++20	0 / 100	1 ms	580 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define sz(v) (int)v.size()
const int MAXN = 1e5+5;
const ll INF = 1e14;
int a[MAXN];
ll dp[2][MAXN], val[MAXN*4], add[MAXN*4], lz[MAXN*4];

void refresh(int node, int l, int r){
    if(lz[node] == 0)return;
    add[node] = lz[node];
    if(l != r){
        lz[node*2] = lz[node];
        lz[node*2+1] = lz[node];
    }
    lz[node] = 0; 
}

void update(int node, int l, int r, int i, int j, int t, ll x){
    refresh(node,l,r);
    if(j < l || r < i)return;
    if(i <= l && r <= j){
        if(t == 0){
            lz[node] = x;
            refresh(node,l,r);
        }else val[node] = x;
        return;
    }

    int mid = (l+r)/2, e = node*2, d = node*2+1;
    update(e,l,mid,i,j,t,x); update(d,mid+1,r,i,j,t,x);
    if(val[e] + add[e] < val[d] + add[d]){
        val[node] = val[e]; add[node] = add[e];
    }else{
        val[node] = val[d]; add[node] = add[d];
    }
}

ll query(int node, int l, int r, int i, int j){
    refresh(node,l,r);
    if(j < l || r < i)return INF;
    if(i <= l && r <= j)return val[node]+add[node];
    int mid = (l+r)/2, e = node*2, d = node*2+1;
    return min( query(e,l,mid,i,j), query(d,mid+1,r,i,j) );
}

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

    int n,K; cin>>n>>K;

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

    for(int i = 1; i <= n; i++)dp[0][i] = INF; dp[0][n+1] = 0;

    for(int k = 1; k <= K; k++){
        vector<int> st;
        dp[k&1][n+1] = INF;
        for(int i = n; i >= 1; i--){
            int r = i;
            while(sz(st) > 0 && a[st.back()] < a[i]){
                st.pop_back();
                if(sz(st) > 0)r = st.back()+1;
                else r = n;
            }
            update(1,1,n, i,r, 0, a[i]);
            st.push_back(i);

            update(1,1,n, i,i, 1, dp[(k-1)&1][i+1]);

            dp[k&1][i] = query(1,1,n, i,n);
        }
    }
    cout<<dp[K&1][1]<<"\n";
}   

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