Submission #1267101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1267101		canhnam357	K blocks (IZhO14_blocks)	C++20	100 / 100	167 ms	1912 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &i : a) cin >> i;
    auto dp = a;
    for (int i = 1; i < n; i++) dp[i] = max(dp[i - 1], dp[i]);
    const int inf = 1e9;
    auto new_dp = dp;
    for (int _ = 1; _ < k; _++) {
        for (int i = 0; i < n; i++) new_dp[i] = inf;
        stack<int> s, t;
        for (int i = 0; i < n; i++) {
            int mx = inf;
            while (!s.empty() && a[s.top()] <= a[i]) {
                mx = min(mx, t.top());
                t.pop();
                s.pop();
            }
            new_dp[i] = min(new_dp[i], mx + a[i]);
            if (!s.empty()) {
                new_dp[i] = min(new_dp[i], dp[s.top()] + a[i]);
                new_dp[i] = min(new_dp[i], new_dp[s.top()]);
            }
            mx = min(mx, dp[i]);
            s.push(i);
            t.push(mx);
        }
        swap(dp, new_dp);
    }   
    cout << dp[n - 1];   
    return 0;
}

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