Submission #503356

#	Time	Username	Problem	Language	Result	Execution time	Memory
503356		lukameladze	K blocks (IZhO14_blocks)	C++14	100 / 100	436 ms	168504 KiB

blocks

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define int long long
#define pii pair <int, int> 
using namespace std;
const int N = 1e5 + 5;
int a[N],n,k,cur,pr[N];
pair <int, int > dp[N][105];
stack < pii > st;
main() {
    cin>>n>>k;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
    }
    dp[0][0] = {0,0};
    for (int i = 1; i <= n; i++) {
        dp[i][0] = {1e9,1e9};
    }
    for (int i = 1; i <= n; i++) {
        cur = i - 1;
        while (a[cur] <= a[i] && cur) {
            cur = pr[cur];
        }
        pr[i] = cur;
    }
    for (int i = 1; i <= k; i++) {
        while (st.size()) st.pop();
        for (int j = i; j <= n; j++) {
            dp[j][i] = {dp[j - 1][i - 1].f + dp[j - 1][i - 1].s, a[j]};
            while (st.size() && st.top().s <= a[j]) {
                if (dp[j][i].f + dp[j][i].s > st.top().f + a[j]) {
                    dp[j][i] = {st.top().f, a[j]};
                }
                st.pop();
            }
            if (pr[j] && pr[j] >= i) {
                if (dp[pr[j]][i].f + dp[pr[j]][i].s < dp[j][i].f + dp[j][i].s) {
                    dp[j][i] = dp[pr[j]][i];
                }
            }
            st.push(dp[j][i]);
        }
    }
    cout<<dp[n][k].f + dp[n][k].s<<endl;
}

Compilation message (stderr)

blocks.cpp:12:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 | main() {
      | ^~~~

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