답안 #88638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
88638	2018-12-07T08:19:28 Z	ABCD	K개의 묶음 (IZhO14_blocks)	C++14	14 / 100	199 ms	45504 KB

blocks

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
const int K=1e2+5;

typedef pair<int,int> ii;

int n,k;
int a[N];
int f[K][N];

void dp(){
    memset(f,1,sizeof(f));
    f[1][0]=0;
    for(int i=1;i<=n;i++) f[1][i]=max(f[1][i-1],a[i]);
    for(int i=2;i<=k;i++){
        stack<ii> st;
        for(int j=i;j<=n;j++){
            int tmp=f[i-1][j-1];
            while(st.size()&&a[st.top().first]<=a[j]){
                tmp=min(tmp,st.top().second);
                st.pop();
            }
            int p=st.size()?st.top().first:0;
            f[i][j]=min(f[i][p],tmp+a[j]);
            st.push({j,tmp});
        }
    }
    cout<<f[k][n];
}

main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    dp();
}

Compilation message

blocks.cpp:33:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1

14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	41464 KB	Output is correct
2	Correct	37 ms	41472 KB	Output is correct
3	Correct	36 ms	41648 KB	Output is correct
4	Correct	36 ms	41704 KB	Output is correct
5	Correct	38 ms	41704 KB	Output is correct
6	Correct	36 ms	41704 KB	Output is correct
7	Correct	34 ms	41704 KB	Output is correct
8	Correct	34 ms	41836 KB	Output is correct
9	Correct	35 ms	41836 KB	Output is correct
10	Correct	36 ms	41836 KB	Output is correct
11	Correct	34 ms	41836 KB	Output is correct
12	Correct	35 ms	41836 KB	Output is correct
13	Correct	34 ms	41836 KB	Output is correct
14	Correct	34 ms	41836 KB	Output is correct
15	Correct	35 ms	41836 KB	Output is correct
16	Correct	33 ms	41836 KB	Output is correct
17	Correct	35 ms	41836 KB	Output is correct
18	Correct	33 ms	41836 KB	Output is correct

Subtask #2

0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	34 ms	41836 KB	Output is correct
2	Correct	34 ms	41836 KB	Output is correct
3	Correct	34 ms	41836 KB	Output is correct
4	Correct	35 ms	41836 KB	Output is correct
5	Correct	38 ms	41836 KB	Output is correct
6	Correct	37 ms	41836 KB	Output is correct
7	Correct	37 ms	41836 KB	Output is correct
8	Correct	38 ms	41836 KB	Output is correct
9	Correct	34 ms	41836 KB	Output is correct
10	Correct	38 ms	41836 KB	Output is correct
11	Correct	38 ms	41836 KB	Output is correct
12	Correct	34 ms	41840 KB	Output is correct
13	Correct	35 ms	41856 KB	Output is correct
14	Correct	37 ms	41856 KB	Output is correct
15	Correct	39 ms	41872 KB	Output is correct
16	Correct	37 ms	41872 KB	Output is correct
17	Correct	37 ms	41872 KB	Output is correct
18	Correct	62 ms	41872 KB	Output is correct
19	Correct	34 ms	41880 KB	Output is correct
20	Incorrect	33 ms	41880 KB	Output isn't correct

Subtask #3

0 / 21.0

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

Subtask #4

0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	40 ms	41880 KB	Output is correct
2	Correct	40 ms	42668 KB	Output is correct
3	Correct	44 ms	42932 KB	Output is correct
4	Correct	91 ms	43264 KB	Output is correct
5	Correct	199 ms	44212 KB	Output is correct
6	Correct	50 ms	44808 KB	Output is correct
7	Correct	116 ms	45504 KB	Output is correct
8	Correct	34 ms	45504 KB	Output is correct
9	Incorrect	36 ms	45504 KB	Output isn't correct
10	Halted	0 ms	0 KB	-