Submission #1026028

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026028		vjudge1	K blocks (IZhO14_blocks)	C++17	53 / 100	1061 ms	178512 KiB

blocks

#include "bits/stdc++.h"
using namespace std;
    
//#define int int64_t
#define pb push_back

const int lim=2e5+100;
int mod=1e9+7;

const int inf=INT_MAX;

using pii=pair<int,int>;

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int dp[k+1][n];
    dp[1][0]=a[0];
    for(int i=1;i<n;i++){
        dp[1][i]=max(dp[1][i-1],a[i]);
    }
    if(k==1){
        cout<<dp[1][n-1];
        return 0;
    }
    int val[k+1][n];
    vector<int>stk;
    stk.pb(-1);
    multiset<int>goodvals[k+1];
    for(int i=0;i<=k;i++){
        goodvals[i].insert(inf);
    }
    for(int i=0;i<n;i++){
        for(int j=2;j<=k;j++){
            if(i)val[j][i]=dp[j-1][i-1];
            else val[j][i]=inf;
        }
        while(stk.back()!=-1&&a[stk.back()]<a[i]){
            for(int j=2;j<=k;j++){
                if(val[j][stk.back()]!=inf){
                    val[j][i]=min(val[j][i],val[j][stk.back()]-a[stk.back()]);
                    goodvals[j].erase(goodvals[j].find(val[j][stk.back()]));
                }
            }
            stk.pop_back();
        }
        for(int j=2;j<=k;j++){
            if(val[j][i]!=inf){
                val[j][i]+=a[i];
                goodvals[j].insert(val[j][i]);
            }
        }
        for(int j=2;j<=k;j++){
            dp[j][i]=*goodvals[j].begin();
        }
        stk.pb(i);
    }
    cout<<dp[k][n-1];
}

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