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
#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;
}
# 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
# 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
# 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
# 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