Submission #1306140

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306140		Sofiatpc	K개의 묶음 (IZhO14_blocks)	C++20	53 / 100	1096 ms	4612 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], mn[MAXN*4], mndp[MAXN*4], lz[MAXN*4];

void refresh(int node, int l, int r){
    if(lz[node] == 0)return;
    mndp[node] = mn[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 mn[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);
    mndp[node] = min(mndp[e], mndp[d]);
    mn[node] = min(mn[e], mn[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 mndp[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--){
            update(1,1,n, i,i, 1, dp[(k-1)&1][i+1]);

            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);

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

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