Submission #1228008

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228008		Hamed_Ghaffari	K blocks (IZhO14_blocks)	C++20	100 / 100	108 ms	4556 KiB

blocks

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

using pii = pair<int, int>;

const int MXN = 1e5+5;

int n, k, a[MXN], L[MXN], R[MXN], lc[MXN], rc[MXN], dp[2][MXN];

inline pii gp(int i) { return pii(a[i], i); }

int calc(int i, int val) {
    if(lc[i]) {
        int mnl = calc(lc[i], val);
        dp[1][i] = min(val, mnl+a[i]);
        if(rc[i])
            return min({mnl, dp[0][i], calc(rc[i], min(dp[1][i], dp[0][L[i]]+a[i]))});
        return min(mnl, dp[0][i]);
    }
    dp[1][i] = min(val, dp[0][i-1]+a[i]);
    if(rc[i])
        return min(dp[0][i], calc(rc[i], dp[1][i]));
    return dp[0][i];
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        dp[1][i] = max(dp[1][i-1], a[i]);
        for(L[i]=i-1; L[i]>=1 && gp(L[i])<gp(i); L[i]=L[L[i]]);
    }
    for(int i=n; i>=1; i--)
        for(R[i]=i+1; R[i]<=n && gp(R[i])<gp(i); R[i]=R[R[i]]);
    int root = 0;
    for(int i=1; i<=n; i++)
        if(L[i]==0) {
            if(R[i]==n+1) root=i;
            else lc[R[i]] = i;
        }
        else if(R[i]==n+1 || gp(L[i])<gp(R[i])) rc[L[i]] = i;
        else lc[R[i]] = i;
    dp[0][0] = dp[1][0] = 1e9;
    for(int i=2; i<=k; i++) {
        for(int j=1; j<=n; j++)
            dp[0][j] = dp[1][j],
            dp[1][j] = 1e9;
        calc(root, 1e9);
    }
    cout << dp[1][n] << '\n';
}

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