Submission #870491

#	Time	Username	Problem	Language	Result	Execution time	Memory
870491		hazzu	K blocks (IZhO14_blocks)	C++17	100 / 100	156 ms	41712 KiB

blocks

#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> ii;
const int inf = 1e9;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int n, k; cin >> n >> k;
    vector<int> a(n + 1, inf);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    vector<vi> dp(k + 1, vi(n + 1, inf));
    
    dp[0][0] = 0;
    for (int j = 1; j <= k; j++) {
        stack<ii> stk;
        for (int i = j; i <= n; i++) {
            int minF = dp[j - 1][i - 1];
            while (!stk.empty() && a[stk.top().st] < a[i]) {
                minF = min(minF, stk.top().nd);
                stk.pop();
            }
            
            dp[j][i] = minF + a[i];
            if (!stk.empty()) dp[j][i] = min(dp[j][i], dp[j][stk.top().st]);
            stk.push({i, minF});
        }
    }    
    
    cout << dp[k][n];
    return 0;
}

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