제출 #1026034

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1026034		vjudge1	K개의 묶음 (IZhO14_blocks)	C++17	100 / 100	165 ms	117460 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);
    vector<pii>goodvals[k+1];
    for(int i=0;i<=k;i++){
        goodvals[i].pb({inf,-1});
    }
    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()]);
                    if(goodvals[j].back().second==stk.back())goodvals[j].pop_back();
                }
            }
            stk.pop_back();
        }
        for(int j=2;j<=k;j++){
            if(val[j][i]!=inf){
                val[j][i]+=a[i];
                if(val[j][i]<goodvals[j].back().first)goodvals[j].pb({val[j][i],i});
            }
        }
        for(int j=2;j<=k;j++){
            dp[j][i]=goodvals[j].back().first;
        }
        stk.pb(i);
    }
    cout<<dp[k][n-1];
}

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