Submission #294678

#	Time	Username	Problem	Language	Result	Execution time	Memory
294678		phathnv	K개의 묶음 (IZhO14_blocks)	C++11	100 / 100	142 ms	40824 KiB

blocks

#include <bits/stdc++.h>

#define mp make_pair
#define X first
#define Y second

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int K = 101;
const int INF = 1e9;

int n, k, h[N];

int top, dp[K][N];
ii St[N];

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

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

    dp[1][1] = h[1];
    for(int i = 2; i <= n; i++)
        dp[1][i] = max(dp[1][i - 1], h[i]);
    for(int c = 2; c <= k; c++){
        top = 0;
        h[c - 1] = INF;
        dp[c][c - 1] = INF;
        St[++top] = mp(c - 1, dp[c - 1][c - 1]);
        for(int i = c; i <= n; i++){
            while (h[i] >= h[St[top].X]){
                St[top - 1].Y = min(St[top - 1].Y, St[top].Y);
                top--;
            }
            dp[c][i] = min(dp[c][St[top].X], St[top].Y + h[i]);
            St[++top] = mp(i, dp[c - 1][i]);
        }
    }

    cout << dp[k][n];

    return 0;
}

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