oj.uz

Submission #173031

# Submission time Handle Problem Language Result Execution time Memory
173031 2020-01-03T06:08:08 Z juggernaut K blocks (IZhO14_blocks) C++14
0 / 100
 46 ms 39932 KB 
//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);
    memset(dp,0x3f,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]=0x3f;
    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 Correct 35 ms 39800 KB Output is correct
2 Correct 35 ms 39928 KB Output is correct
3 Correct 35 ms 39800 KB Output is correct
4 Correct 36 ms 39876 KB Output is correct
5 Correct 36 ms 39928 KB Output is correct
6 Correct 36 ms 39800 KB Output is correct
7 Correct 35 ms 39800 KB Output is correct
8 Correct 36 ms 39800 KB Output is correct
9 Correct 44 ms 39800 KB Output is correct
10 Correct 42 ms 39800 KB Output is correct
11 Correct 36 ms 39892 KB Output is correct
12 Correct 37 ms 39800 KB Output is correct
13 Incorrect 36 ms 39844 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 39932 KB Output is correct
2 Correct 36 ms 39800 KB Output is correct
3 Correct 36 ms 39800 KB Output is correct
4 Correct 36 ms 39800 KB Output is correct
5 Correct 36 ms 39800 KB Output is correct
6 Correct 36 ms 39928 KB Output is correct
7 Correct 36 ms 39800 KB Output is correct
8 Correct 36 ms 39928 KB Output is correct
9 Correct 35 ms 39800 KB Output is correct
10 Correct 36 ms 39800 KB Output is correct
11 Correct 46 ms 39928 KB Output is correct
12 Correct 35 ms 39800 KB Output is correct
13 Correct 35 ms 39800 KB Output is correct
14 Incorrect 35 ms 39800 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 39800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 39928 KB Output isn't correct
2 Halted 0 ms 0 KB -