제출 #1171551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171551		AlgorithmWarrior	K개의 묶음 (IZhO14_blocks)	C++20	100 / 100	138 ms	3228 KiB

blocks

#include <bits/stdc++.h>

using namespace std;

int const MAX=1e5+5;
long long dp[MAX];
long long old_dp[MAX];
int n,k;
int v[MAX];

void read(){
    cin>>n>>k;
    int i;
    for(i=1;i<=n;++i)
        cin>>v[i];
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

struct structy{
    int val;
    long long old,dp;
};

void upgrade(){
    int i;
    for(i=0;i<=n;++i)
        old_dp[i]=dp[i];
    stack<structy>stv;
    for(i=1;i<=n;++i){
        long long old=old_dp[i-1];
        while(!stv.empty() && stv.top().val<=v[i]){
            minself(old,stv.top().old);
            stv.pop();
        }
        dp[i]=old+v[i];
        if(!stv.empty())
            minself(dp[i],stv.top().dp);
        stv.push({v[i],old,dp[i]});
    }
}

int solve(){
    dp[0]=1e18;
    dp[1]=v[1];
    int i;
    for(i=2;i<=n;++i)
        dp[i]=max((int)dp[i-1],v[i]);
    for(i=2;i<=k;++i)
        upgrade();
    return dp[n];
}

int main()
{
    read();
    cout<<solve();
    return 0;
}

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