| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 88638 |
2018-12-07T08:19:28 Z |
ABCD |
K blocks (IZhO14_blocks) |
C++14 |
|
199 ms |
45504 KB |
#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(){
^
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
41880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
