제출 #889645

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
889645		dwuy	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	181 ms	3028 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;

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, mn, mnf;
        a[j-1] = INF;
        st.push(j-1);
        mn.push(INF);
        mnf.push(INF);
        for(int i=j; i<=n; i++){
            int val = pre[i-1];
            while(a[st.top()] <= a[i]){
                st.pop();
                mn.pop();
                val = min(val, mnf.top());
                mnf.pop();
            }
            mn.push(min(mn.top(), val+a[i]));
            mnf.push(val);
            st.push(i);
            cur[i] = mn.top();
        }
        for(int i=j; i<=n; i++) pre[i] = cur[i];
    }
    cout << pre[n];
}

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

    nhap();
    solve();

    return 0;
}

/**

5 3
5 7 10 3 5

**/

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