Submission #1326047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326047		hokageoftheleaf	K blocks (IZhO14_blocks)	C++20	100 / 100	126 ms	3564 KiB

blocks

#include <bits/stdc++.h>
using namespace std;

const long long INF = (long long)4e18;

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

    int N, K;
    cin >> N >> K;
    vector<int> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    vector<long long> dp_prev(N + 1, INF), dp_cur(N + 1, INF);
    vector<long long> best(N + 1, INF);
    vector<int> pre(N + 1, 0);

    dp_prev[0] = 0;

    for (int k = 1; k <= K; k++) {

        for (int i = 1; i <= N; i++) {

            int p = i - 1;
            while (p > 0 && A[p] <= A[i]) p = pre[p];
            pre[i] = p;

            
            dp_cur[i] = dp_prev[i - 1] + A[i];
            best[i] = dp_cur[i];

            
            if (pre[i] != 0) {
                int j = pre[i];
                best[i] = min(best[i], best[j]);
            }

            int j = i - 1;
            while (j > 0 && A[j] <= A[i]) {
                best[i] = min(best[i], best[j] - A[j] + A[i]);
                j = pre[j];
            }

            dp_cur[i] = best[i];
        }

        dp_prev = dp_cur;
        fill(dp_cur.begin(), dp_cur.end(), INF);
    }

    cout << dp_prev[N];
}

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