제출 #659821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
659821		stevancv	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	385 ms	7120 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const int inf = 2e9;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    vector<vector<int>> gr(n);
    stack<int> s;
    vector<int> v;
    for (int i = 0; i < n; i++) {
        while (!s.empty() && a[s.top()] < a[i]) s.pop();
        if (!s.empty()) gr[s.top()].push_back(i);
        else v.push_back(i);
        s.push(i);
    }
    while (!s.empty()) s.pop();
    vector<int> dp(n + 1, inf);
    dp[0] = 0;
    while (k--) {
        vector<int> f(n, inf), g(n, inf);
        for (int i = 0; i < n; i++) {
            while (!s.empty() && a[s.top()] <= a[i]) {
                smin(f[i], min(f[s.top()], dp[s.top() + 1]));
                s.pop();
            }
            if (s.empty()) smin(f[i], dp[0]);
            s.push(i);
        }
        while (!s.empty()) s.pop();
        queue<int> q;
        for (int i : v) q.push(i);
        while (!q.empty()) {
            int s = q.front(); q.pop();
            for (int u : gr[s]) {
                g[u] = min(g[s], dp[s + 1]);
                q.push(u);
            }
        }
        for (int i = 0; i <= n; i++) dp[i] = inf;
        for (int i = 1; i <= n; i++) {
            dp[i] = min(f[i - 1], g[i - 1]) + a[i - 1];
        }
    }
    int ans = inf;
    int mx = -inf;
    for (int i = n - 1; i >= 0; i--) {
        smax(mx, a[i]);
        if (a[i] == mx) smin(ans, dp[i + 1]);
    }
    cout << ans << en;
    return 0;
}

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