Submission #1191231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191231		ttamx	K blocks (IZhO14_blocks)	C++20	100 / 100	193 ms	5124 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=1e5+5;

int n,k;
ll a[N],dp[2][N];

struct Info{
    ll mx,opt,mn;
};

int main() {
    cin >> n >> k;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    for(int i=1;i<=n;i++){
        dp[1][i]=max(dp[1][i-1],a[i]);
    }
    for(int s=2;s<=k;s++){
        int cur=s%2,pre=1-cur;
        vector<Info> st;
        for(int i=s;i<=n;i++){
            Info res{a[i],dp[pre][i-1]+a[i],0LL};
            while(!st.empty()&&st.back().mx<=a[i]){
                Info tmp=st.back();
                st.pop_back();
                ll diff=a[i]-tmp.mx;
                res.opt=min(res.opt,tmp.opt+diff);
            }
            res.mn=res.opt;
            if(!st.empty()){
                res.mn=min(res.mn,st.back().mn);
            }
            st.push_back(res);
            dp[cur][i]=res.mn;
        }
    }
    cout << dp[k%2][n] << "\n";
}

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