oj.uz

답안 #173031

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
173031 2020-01-03T06:08:08 Z juggernaut K개의 묶음 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

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

Subtask #4
0 / 47.0

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