Submission #146382

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
146382	2019-08-23T16:08:56 Z	abacaba	K blocks (IZhO14_blocks)	C++14	100 / 100	347 ms	92720 KB

blocks

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <math.h>
#include <utility>
#include <set>
#include <time.h>
#include <list>
#include <typeinfo>
#include <cstdio>
#include <numeric>
#include <stack>
#include <stdio.h>
using namespace std;
 
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>

const ll inf = 2e18;
const int N = 1e5 + 15;
const int K = 115;
ll n, k, a[N], dp[K][N], maxx;
stack <ll> s[2];

int main() {
	for(int i = 0; i < K; ++i)
		for(int j = 0; j < N; ++j)
			dp[i][j] = inf;
	cin >> n >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		maxx = max(maxx, a[i]);
		dp[1][i] = maxx;
	}
	for(int i = 2; i <= k; ++i) {
		while(!s[0].empty())
			s[0].pop(), s[1].pop();
		for(int j = 1; j <= n; ++j) {
			ll cur = dp[i - 1][j - 1];
			while(!s[0].empty() && s[0].top() < a[j]) {
				cur = min(cur, s[1].top());
				s[0].pop(), s[1].pop();
			}
			if(s[0].empty() || s[0].top() + s[1].top() > cur + a[j])
				s[0].push(a[j]), s[1].push(cur);

			if(j >= i)
				dp[i][j] = s[0].top() + s[1].top();
		}
	}
	cout << dp[k][n] << endl;
	return 0;
}

Subtask #1
14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	90360 KB	Output is correct
2	Correct	73 ms	90360 KB	Output is correct
3	Correct	74 ms	90488 KB	Output is correct
4	Correct	73 ms	90508 KB	Output is correct
5	Correct	73 ms	90360 KB	Output is correct
6	Correct	74 ms	90344 KB	Output is correct
7	Correct	74 ms	90360 KB	Output is correct
8	Correct	74 ms	90280 KB	Output is correct
9	Correct	74 ms	90360 KB	Output is correct
10	Correct	73 ms	90332 KB	Output is correct
11	Correct	74 ms	90444 KB	Output is correct
12	Correct	74 ms	90360 KB	Output is correct
13	Correct	74 ms	90360 KB	Output is correct
14	Correct	74 ms	90360 KB	Output is correct
15	Correct	74 ms	90360 KB	Output is correct
16	Correct	74 ms	90360 KB	Output is correct
17	Correct	75 ms	90360 KB	Output is correct
18	Correct	74 ms	90520 KB	Output is correct

Subtask #2
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	90360 KB	Output is correct
2	Correct	73 ms	90364 KB	Output is correct
3	Correct	74 ms	90360 KB	Output is correct
4	Correct	75 ms	90488 KB	Output is correct
5	Correct	74 ms	90360 KB	Output is correct
6	Correct	75 ms	90336 KB	Output is correct
7	Correct	75 ms	90488 KB	Output is correct
8	Correct	74 ms	90332 KB	Output is correct
9	Correct	75 ms	90384 KB	Output is correct
10	Correct	77 ms	90360 KB	Output is correct
11	Correct	74 ms	90340 KB	Output is correct
12	Correct	74 ms	90360 KB	Output is correct
13	Correct	74 ms	90360 KB	Output is correct
14	Correct	74 ms	90360 KB	Output is correct
15	Correct	90 ms	90360 KB	Output is correct
16	Correct	88 ms	90360 KB	Output is correct
17	Correct	89 ms	90332 KB	Output is correct
18	Correct	89 ms	90312 KB	Output is correct
19	Correct	80 ms	90344 KB	Output is correct
20	Correct	77 ms	90432 KB	Output is correct

Subtask #3
21.0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	65 ms	90364 KB	Output is correct
2	Correct	75 ms	90360 KB	Output is correct
3	Correct	74 ms	90360 KB	Output is correct
4	Correct	75 ms	90616 KB	Output is correct
5	Correct	74 ms	90360 KB	Output is correct
6	Correct	75 ms	90360 KB	Output is correct
7	Correct	77 ms	90360 KB	Output is correct
8	Correct	77 ms	90360 KB	Output is correct
9	Correct	76 ms	90360 KB	Output is correct
10	Correct	75 ms	90332 KB	Output is correct
11	Correct	75 ms	90460 KB	Output is correct
12	Correct	75 ms	90332 KB	Output is correct
13	Correct	79 ms	90392 KB	Output is correct
14	Correct	76 ms	90332 KB	Output is correct
15	Correct	76 ms	90488 KB	Output is correct
16	Correct	75 ms	90360 KB	Output is correct
17	Correct	76 ms	90360 KB	Output is correct
18	Correct	76 ms	90488 KB	Output is correct
19	Correct	76 ms	90360 KB	Output is correct

Subtask #4
47.0 / 47.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	94 ms	90488 KB	Output is correct
2	Correct	100 ms	91096 KB	Output is correct
3	Correct	104 ms	91100 KB	Output is correct
4	Correct	136 ms	90952 KB	Output is correct
5	Correct	244 ms	91768 KB	Output is correct
6	Correct	129 ms	91868 KB	Output is correct
7	Correct	177 ms	91868 KB	Output is correct
8	Correct	76 ms	90404 KB	Output is correct
9	Correct	75 ms	90360 KB	Output is correct
10	Correct	81 ms	90360 KB	Output is correct
11	Correct	75 ms	90360 KB	Output is correct
12	Correct	76 ms	90360 KB	Output is correct
13	Correct	76 ms	90360 KB	Output is correct
14	Correct	92 ms	90564 KB	Output is correct
15	Correct	80 ms	90492 KB	Output is correct
16	Correct	83 ms	90460 KB	Output is correct
17	Correct	99 ms	91000 KB	Output is correct
18	Correct	102 ms	91000 KB	Output is correct
19	Correct	135 ms	91000 KB	Output is correct
20	Correct	229 ms	91888 KB	Output is correct
21	Correct	133 ms	91896 KB	Output is correct
22	Correct	175 ms	91860 KB	Output is correct
23	Correct	130 ms	91856 KB	Output is correct
24	Correct	140 ms	91760 KB	Output is correct
25	Correct	234 ms	91988 KB	Output is correct
26	Correct	76 ms	90360 KB	Output is correct
27	Correct	91 ms	90360 KB	Output is correct
28	Correct	110 ms	90708 KB	Output is correct
29	Correct	82 ms	90560 KB	Output is correct
30	Correct	86 ms	90616 KB	Output is correct
31	Correct	101 ms	91000 KB	Output is correct
32	Correct	106 ms	91384 KB	Output is correct
33	Correct	165 ms	91452 KB	Output is correct
34	Correct	347 ms	92696 KB	Output is correct
35	Correct	136 ms	92536 KB	Output is correct
36	Correct	224 ms	92720 KB	Output is correct
37	Correct	80 ms	90488 KB	Output is correct
38	Correct	93 ms	90460 KB	Output is correct
39	Correct	75 ms	90488 KB	Output is correct
40	Correct	75 ms	90336 KB	Output is correct
41	Correct	88 ms	90360 KB	Output is correct
42	Correct	82 ms	90300 KB	Output is correct

Submission #146382

Compilation message

Subtask #1 14.0 / 14.0

Subtask #2 18.0 / 18.0

Subtask #3 21.0 / 21.0

Subtask #4 47.0 / 47.0

Subtask #1
14.0 / 14.0

Subtask #2
18.0 / 18.0

Subtask #3
21.0 / 21.0

Subtask #4
47.0 / 47.0