Submission #173033

#	Time	Username	Problem	Language	Result	Execution time	Memory
173033		juggernaut	K blocks (IZhO14_blocks)	C++14	100 / 100	269 ms	40712 KiB

blocks

//Just try and the idea will come!
#include<bits/stdc++.h>
using namespace std;
int dp[101][100001],n,k,i,a[100001],j,tmp;
main(){
    scanf("%d%d",&n,&k);
    for(i=0;i<101;i++)
        for(j=0;j<100001;j++)dp[i][j]=1e8;
    dp[1][0]=0;
    for(i=1;i<=n;i++)scanf("%d",&a[i]),dp[1][i]=max(dp[1][i-1],a[i]);
    dp[1][0]=1e8;
    for(i=2;i<=k;i++){
        stack<pair<int,int>>st;
        for(j=i;j<=n;j++){
            tmp=dp[i-1][j-1];
            while(!st.empty()&&a[st.top().first]<a[j]){
                tmp=min(tmp,st.top().second);
                st.pop();
            }
            if(!st.empty()&&j>=i)dp[i][j]=dp[i][st.top().first];
            st.push({j,min(dp[i-1][j],tmp)});
            if(j>=i)dp[i][j]=min(dp[i][j],tmp+a[j]);
        }
    }
    printf("%d",dp[k][n]);
}

Compilation message (stderr)

blocks.cpp:5:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
blocks.cpp: In function 'int main()':
blocks.cpp:6:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&k);
     ~~~~~^~~~~~~~~~~~~~
blocks.cpp:10:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=n;i++)scanf("%d",&a[i]),dp[1][i]=max(dp[1][i-1],a[i]);
                      ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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