제출 #1306342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306342		Sofiatpc	K blocks (IZhO14_blocks)	C++20	100 / 100	972 ms	4756 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];

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> p; vector<ll> pmn;
        multiset<ll> st;
        dp[k&1][n+1] = INF;
        for(int i = n; i >= 1; i--){
            ll mn = dp[(k-1)&1][i+1];
            while(sz(p) > 0 && a[p.back()] <= a[i]){
                mn = min(mn, pmn.back());
                st.erase( st.find(pmn.back() + a[p.back()]) );
                p.pop_back(); pmn.pop_back();
            }
            
            p.push_back(i); pmn.push_back(mn);
            st.insert(mn + a[i]);

            dp[k&1][i] = min(INF,*st.begin());
        }
    }
    cout<<dp[K&1][1]<<"\n";
}   

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