제출 #171756

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171756		VEGAnn	K blocks (IZhO14_blocks)	C++14	100 / 100	354 ms	45044 KiB

blocks

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define PB push_back
#define MP make_pair
#define ft first
#define sd second
#define pii pair<int, int>
#define pi3 pair<pii, int>
#define MP3(a,b,c) MP(MP(a, b), c)
using namespace std;
const int oo = 1e9;
const int N = 100100;
const int K = 110;
const int PW = 20;
stack<pi3> st;
int f[N][K], a[N], n, k;

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[0] = oo;

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= k; j++)
            f[i][j] = oo;

    f[0][0] = 0;

    for (int j = 1; j <= k; j++) {
        while (sz(st)) st.pop();

        st.push(MP3(0, oo, oo));

        for (int i = 1; i <= n; i++){

            pi3 nw = MP3(i, f[i - 1][j - 1], 0);

            while (a[st.top().ft.ft] <= a[i]) {
                nw.ft.sd = min(nw.ft.sd, st.top().ft.sd);
                st.pop();
            }

            nw.sd = min(st.top().sd, nw.ft.sd + a[i]);
            st.push(nw);

            f[i][j] = nw.sd;
        }
    }

    cout << f[n][k];
    return 0;
}

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