oj.uz

답안 #173030

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173030 2020-01-03T06:05:58 Z juggernaut K개의 묶음 (IZhO14_blocks) C++14
0 / 100
 42 ms 40060 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,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

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 39800 KB Output is correct
2 Correct 36 ms 39928 KB Output is correct
3 Correct 36 ms 39928 KB Output is correct
4 Incorrect 35 ms 39800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 40060 KB Output is correct
2 Correct 35 ms 39800 KB Output is correct
3 Correct 35 ms 39928 KB Output is correct
4 Incorrect 30 ms 39928 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 36 ms 39828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 39960 KB Output isn't correct
2 Halted 0 ms 0 KB -