oj.uz

Submission #82991

# Submission time Handle Problem Language Result Execution time Memory
82991 2018-11-03T13:43:19 Z rezolden K blocks (IZhO14_blocks) C++14
100 / 100
 498 ms 56892 KB 
#include <bits/stdc++.h>

#define maxn 100010
#define maxk 110
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)

typedef long long ll;
using namespace std;
const char *fi="BLOCKS.INP";
const char *fo="BLOCKS.OUT";
const int oo=1e9;

int n,k,A[maxn],P[maxn],F[maxn][maxk];
stack<pair<int,int> > Q;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//	freopen(fi,"r",stdin);
//	freopen(fo,"w",stdout);
    cin>>n>>k;
    FOR(i,1,n) cin>>A[i];
    P[0]=0;
    FOR(i,1,n) P[i]=max(P[i-1],A[i]);

    FOR(i,1,n) F[i][1]=P[i];
    FOR(j,2,k){
        F[0][j]=oo;
        while (!Q.empty()) Q.pop();
        FOR(i,j,n){
            int tmp = F[i-1][j-1];
            while (!Q.empty() && A[Q.top().second]<=A[i]){
                tmp = min(tmp,Q.top().first);
                Q.pop();
            }
            F[i][j] = min(F[Q.empty()?0:Q.top().second][j], tmp+A[i]);
            Q.push({tmp,i});
        }
    }

    cout<<F[n][k];
	return 0;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 2 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 576 KB Output is correct
8 Correct 2 ms 580 KB Output is correct
9 Correct 2 ms 584 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 592 KB Output is correct
12 Correct 2 ms 724 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Correct 2 ms 772 KB Output is correct
16 Correct 2 ms 772 KB Output is correct
17 Correct 2 ms 772 KB Output is correct
18 Correct 2 ms 772 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 772 KB Output is correct
2 Correct 2 ms 796 KB Output is correct
3 Correct 2 ms 796 KB Output is correct
4 Correct 3 ms 796 KB Output is correct
5 Correct 2 ms 796 KB Output is correct
6 Correct 2 ms 856 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 856 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 2 ms 856 KB Output is correct
12 Correct 2 ms 1024 KB Output is correct
13 Correct 2 ms 1024 KB Output is correct
14 Correct 2 ms 1024 KB Output is correct
15 Correct 2 ms 1024 KB Output is correct
16 Correct 2 ms 1024 KB Output is correct
17 Correct 2 ms 1024 KB Output is correct
18 Correct 2 ms 1084 KB Output is correct
19 Correct 2 ms 1084 KB Output is correct
20 Correct 2 ms 1084 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1084 KB Output is correct
2 Correct 2 ms 1132 KB Output is correct
3 Correct 2 ms 1132 KB Output is correct
4 Correct 2 ms 1136 KB Output is correct
5 Correct 2 ms 1140 KB Output is correct
6 Correct 2 ms 1144 KB Output is correct
7 Correct 2 ms 1148 KB Output is correct
8 Correct 3 ms 1152 KB Output is correct
9 Correct 2 ms 1156 KB Output is correct
10 Correct 2 ms 1252 KB Output is correct
11 Correct 2 ms 1252 KB Output is correct
12 Correct 2 ms 1252 KB Output is correct
13 Correct 2 ms 1252 KB Output is correct
14 Correct 2 ms 1252 KB Output is correct
15 Correct 2 ms 1252 KB Output is correct
16 Correct 2 ms 1252 KB Output is correct
17 Correct 2 ms 1252 KB Output is correct
18 Correct 3 ms 1252 KB Output is correct
19 Correct 2 ms 1252 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5552 KB Output is correct
2 Correct 23 ms 20980 KB Output is correct
3 Correct 26 ms 21356 KB Output is correct
4 Correct 69 ms 21604 KB Output is correct
5 Correct 198 ms 46760 KB Output is correct
6 Correct 55 ms 47456 KB Output is correct
7 Correct 111 ms 48012 KB Output is correct
8 Correct 2 ms 48012 KB Output is correct
9 Correct 3 ms 48012 KB Output is correct
10 Correct 2 ms 48012 KB Output is correct
11 Correct 2 ms 48012 KB Output is correct
12 Correct 3 ms 48012 KB Output is correct
13 Correct 3 ms 48012 KB Output is correct
14 Correct 22 ms 48012 KB Output is correct
15 Correct 7 ms 48012 KB Output is correct
16 Correct 14 ms 48012 KB Output is correct
17 Correct 21 ms 48012 KB Output is correct
18 Correct 28 ms 48012 KB Output is correct
19 Correct 84 ms 48012 KB Output is correct
20 Correct 253 ms 50040 KB Output is correct
21 Correct 50 ms 50588 KB Output is correct
22 Correct 168 ms 51392 KB Output is correct
23 Correct 62 ms 51984 KB Output is correct
24 Correct 64 ms 52624 KB Output is correct
25 Correct 498 ms 53436 KB Output is correct
26 Correct 3 ms 53436 KB Output is correct
27 Correct 3 ms 53436 KB Output is correct
28 Correct 21 ms 53436 KB Output is correct
29 Correct 6 ms 53436 KB Output is correct
30 Correct 12 ms 53436 KB Output is correct
31 Correct 27 ms 53436 KB Output is correct
32 Correct 26 ms 53436 KB Output is correct
33 Correct 75 ms 53436 KB Output is correct
34 Correct 246 ms 55524 KB Output is correct
35 Correct 51 ms 56208 KB Output is correct
36 Correct 126 ms 56892 KB Output is correct
37 Correct 7 ms 56892 KB Output is correct
38 Correct 18 ms 56892 KB Output is correct
39 Correct 2 ms 56892 KB Output is correct
40 Correct 2 ms 56892 KB Output is correct
41 Correct 2 ms 56892 KB Output is correct
42 Correct 2 ms 56892 KB Output is correct