oj.uz

Submission #173029

# Submission time Handle Problem Language Result Execution time Memory
173029 2020-01-03T06:04:06 Z juggernaut K blocks (IZhO14_blocks) C++14
0 / 100
 223 ms 262148 KB 
//Just try and the idea will come!
#include<bits/stdc++.h>
using namespace std;
int dp[101][1000001],n,k,i,a[1000001],j,tmp;
main(){
    scanf("%d%d",&n,&k);
    memset(dp,1e8,sizeof(dp));
    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=1;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

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:9: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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 217 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 218 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 214 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -