Submission #465284

#	Time	Username	Problem	Language	Result	Execution time	Memory
465284		NintsiChkhaidze	K blocks (IZhO14_blocks)	C++14	100 / 100	322 ms	84692 KiB

blocks

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pi pair<ll,ll>
#define s second
#define f first
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;

const int N = 200005;
ll a[N],dp[N][105];
stack <pi> st;

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    
    int n,k;
    cin>>n>>k;
    
    for (int i = 1; i <= n; i++){
        cin>>a[i];
        dp[i][1] = max(dp[i - 1][1], a[i]);
    }
    
    for (int K = 2; K <= k; K++){
        while(st.size())    
            st.pop();
            
        for (int j = K; j <= n; j++){
            ll d = dp[j - 1][K - 1];
            
            while(st.size() && a[j] > st.top().f){
                d = min(d, st.top().s);
                st.pop();
            }
            
            if (!st.size() || st.top().f + st.top().s > a[j] + d)
                st.push({a[j],d});
            
            dp[j][K] = st.top().f + st.top().s;
        }
    }
    
    cout<<dp[n][k];
}

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