Submission #1291452

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291452		Art	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	129 ms	43008 KiB

blocks

//      - Art -
#include <bits/stdc++.h>

#define el              cout << '\n'

#define FOR(i, a, b)    for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a)    for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c)       for (int i = 0, _c = (c); i < _c; ++i)

const int N = 1e5 + 7;

using namespace std;

int a[N];
int dp[107][N];

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, k;
    cin >> n >> k;
    FOR (i, 1, n) {
        cin >> a[i];
    }

    memset(dp, 0x3f, sizeof dp);
    dp[1][0] = 0;
    FOR (i, 1, n) {
        dp[1][i] = max(dp[1][i - 1], a[i]);
    }
    FOR (i, 2, k) {
        stack<pair<int, int> > S;
        FOR (j, i, n) {
            int minF = dp[i - 1][j - 1];
            while (!S.empty() && a[S.top().second] <= a[j]) {
                minF = min(minF, S.top().first);
                S.pop();
            }
            dp[i][j] = min(dp[i][S.empty() ? 0 : S.top().second], minF + a[j]);
            S.push(make_pair(minF, j));
        }
    }
    cout << dp[k][n], el;

    return 0;
}

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