Submission #251420

#	Time	Username	Problem	Language	Result	Execution time	Memory
251420		thecodingwizard	K blocks (IZhO14_blocks)	C++11	100 / 100	397 ms	81272 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n, k; cin >> n >> k;
    int A[n+1]; for (int i = 1; i <= n; i++) cin >> A[i];

    ii dp[n+1][k+1];
    dp[0][0] = mp(0, 0);
    for (int i = 1; i <= n; i++) dp[i][0] = mp(1e9, 1e9);
    for (int j = 1; j <= k; j++) {
        stack<ii> s;
        for (int i = j; i <= n; i++) {
            dp[i][j] = mp(dp[i-1][j-1].f+dp[i-1][j-1].s, A[i]);
            while (!s.empty() && s.top().s <= A[i]) {
                if (s.top().f+A[i] < dp[i][j].f+dp[i][j].s) {
                    dp[i][j] = mp(s.top().f, A[i]);
                }
                s.pop();
            }
            if (!s.empty()) {
                if (s.top().f + s.top().s < dp[i][j].f + dp[i][j].s) {
                    dp[i][j] = s.top();
                }
            }
            s.push(dp[i][j]);
        }
    }
    cout << dp[n][k].f + dp[n][k].s << endl;
}

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