제출 #1370097

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370097		domi	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	145 ms	80528 KiB

blocks

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int, int>;

const int NMAX = 1e5;
const int KMAX = 1e2;

using namespace std;

int dp[KMAX + 5][NMAX + 5], a[NMAX + 5], n, k;

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k;

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

    dp[1][0] = INT_MIN;
    for (int i = 1; i <= n; ++i)
        dp[1][i] = max(dp[1][i - 1], a[i]);

    for (int used = 2; used <= k; ++used) {
        stack<array<int, 3>> stk; ///(mx, dp_val, mn_pref)
        for (int i = used; i <= n; ++i) {
            array<int, 3> cur = {a[i], dp[used - 1][i - 1], 0};
            while (!stk.empty() && stk.top()[0] < cur[0]) {
                cur[1] = min(cur[1], stk.top()[1]);
                stk.pop();
            }

            cur[2] = cur[0] + cur[1];
            if (!stk.empty())
                cur[2] = min(cur[2], stk.top()[2]);

            stk.push(cur);
            dp[used][i] = cur[2];
        }
    }

    cout << dp[k][n] << '\n';
    return 0;
}

• 서브태스크 1: 14 / 14
• 서브태스크 2: 18 / 18
• 서브태스크 3: 21 / 21
• 서브태스크 4: 47 / 47