Submission #16199

#	Time	Username	Problem	Language	Result	Execution time	Memory
16199		jihoon	K blocks (IZhO14_blocks)	C++98	100 / 100	137 ms	80896 KiB

blocks

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define inf 500000000
int n,k;
int su[100002];
int dp[100002][101];
int dpp[100002][101];
vector<int> st;
int stp;
int main(){
    int i,j;
    scanf("%d %d",&n,&k);
    for(i=1;i<=n;i++){
        scanf("%d",&su[i]);
    }
    su[0]=inf;
    for(i=0;i<=n;i++){
        for(j=0;j<=k;j++){
            dp[i][j]=inf;
            dpp[i][j]=inf;
        }
    }
    st.push_back(0);
    stp=1;
    for(i=1;i<=n;i++){
        while(stp>0){
            if(su[st[stp-1]]>su[i]) break;
            for(j=0;j<=k;j++){
                dp[st[stp-2]][j]=min(dp[st[stp-2]][j],dp[st[stp-1]][j]);
                if(stp>=3){
                    dpp[st[stp-2]][j]=min(dpp[st[stp-3]][j],dp[st[stp-3]][j]+su[st[stp-2]]);
                }else{
                    dpp[st[stp-2]][j]=inf;
                }
            }
            st.pop_back();
            stp--;
        }
        st.push_back(i);
        stp++;
        dp[i][1]=su[st[1]];
        for(j=1;j<=k-1;j++){
            dpp[i][j]=min(dpp[st[stp-2]][j],dp[st[stp-2]][j]+su[i]);
            dp[i][j+1]=dpp[i][j];
        }
    }
    printf("%d",dp[n][k]);
}

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