답안 #39033 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
39033	2018-01-09T06:06:17 Z	RockyB	K개의 묶음 (IZhO14_blocks)	C++14	100 / 100	516 ms	43424 KB

blocks

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)1e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int get_int() {
	char x = getchar();
	while (!isdigit(x)) x = getchar();
	int res = 0;
	while (isdigit(x)) res = res * 10 + x - '0', x = getchar();
	return res;
}

int n, k;
int a[N];
int dp[101][N];

/*int get_min(int o, int l, int r) {
	int res = dp[o][l];
	for (int i = l + 1; i <= r; i++) {
		res = min(res, dp[o][i]);
	}
	return res;
}*/

int t[N << 1];
void build(int o) {
	for (int i = 0; i <= n; i++) {
		t[i + n] = dp[o][i];
	}
	for (int i = n - 1; i >= 0; i--) {
		t[i] = min(t[i << 1], t[i << 1 | 1]);
	}
}
int get_min(int l, int r) {
	int res = inf;
	for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) res = min(res, t[l++]);
		if (r & 1) res = min(res, t[--r]);
	}
	return res;
}

int sz;
pair <int, int> c[N];
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	n = get_int(), k = get_int();
	for (int i = 1; i <= n; i++) 
		a[i] = get_int();
	memset(dp, 0x3f3f, sizeof(dp));
	dp[0][0] = 0;
	a[0] = inf;
	for (int o = 1; o <= k; o++) {
		sz = 1;
		c[sz] = {0, INT_MAX};
		build(o - 1);
		for (int i = 1; i <= n; i++) {
			while (sz && a[i] >= a[c[sz].f]) {
				sz--;
			}
			c[++sz].f = i;
			c[sz].s = get_min(c[sz - 1].f, c[sz].f - 1) + a[c[sz].f];
			c[sz].s = min(c[sz].s, c[sz - 1].s);
			dp[o][i] = c[sz].s;
		}
	}
	cout << dp[k][n];
	ioi
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	43424 KB	Output is correct
2	Correct	6 ms	43424 KB	Output is correct
3	Correct	3 ms	43424 KB	Output is correct
4	Correct	0 ms	43424 KB	Output is correct
5	Correct	9 ms	43424 KB	Output is correct
6	Correct	3 ms	43424 KB	Output is correct
7	Correct	3 ms	43424 KB	Output is correct
8	Correct	3 ms	43424 KB	Output is correct
9	Correct	9 ms	43424 KB	Output is correct
10	Correct	0 ms	43424 KB	Output is correct
11	Correct	0 ms	43424 KB	Output is correct
12	Correct	0 ms	43424 KB	Output is correct
13	Correct	0 ms	43424 KB	Output is correct
14	Correct	3 ms	43424 KB	Output is correct
15	Correct	0 ms	43424 KB	Output is correct
16	Correct	3 ms	43424 KB	Output is correct
17	Correct	3 ms	43424 KB	Output is correct
18	Correct	0 ms	43424 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	43424 KB	Output is correct
2	Correct	3 ms	43424 KB	Output is correct
3	Correct	3 ms	43424 KB	Output is correct
4	Correct	3 ms	43424 KB	Output is correct
5	Correct	0 ms	43424 KB	Output is correct
6	Correct	0 ms	43424 KB	Output is correct
7	Correct	0 ms	43424 KB	Output is correct
8	Correct	0 ms	43424 KB	Output is correct
9	Correct	0 ms	43424 KB	Output is correct
10	Correct	3 ms	43424 KB	Output is correct
11	Correct	6 ms	43424 KB	Output is correct
12	Correct	6 ms	43424 KB	Output is correct
13	Correct	3 ms	43424 KB	Output is correct
14	Correct	3 ms	43424 KB	Output is correct
15	Correct	6 ms	43424 KB	Output is correct
16	Correct	3 ms	43424 KB	Output is correct
17	Correct	6 ms	43424 KB	Output is correct
18	Correct	3 ms	43424 KB	Output is correct
19	Correct	3 ms	43424 KB	Output is correct
20	Correct	0 ms	43424 KB	Output is correct

Subtask #3
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	43424 KB	Output is correct
2	Correct	0 ms	43424 KB	Output is correct
3	Correct	6 ms	43424 KB	Output is correct
4	Correct	3 ms	43424 KB	Output is correct
5	Correct	3 ms	43424 KB	Output is correct
6	Correct	0 ms	43424 KB	Output is correct
7	Correct	3 ms	43424 KB	Output is correct
8	Correct	3 ms	43424 KB	Output is correct
9	Correct	0 ms	43424 KB	Output is correct
10	Correct	6 ms	43424 KB	Output is correct
11	Correct	0 ms	43424 KB	Output is correct
12	Correct	0 ms	43424 KB	Output is correct
13	Correct	6 ms	43424 KB	Output is correct
14	Correct	3 ms	43424 KB	Output is correct
15	Correct	9 ms	43424 KB	Output is correct
16	Correct	0 ms	43424 KB	Output is correct
17	Correct	3 ms	43424 KB	Output is correct
18	Correct	6 ms	43424 KB	Output is correct
19	Correct	0 ms	43424 KB	Output is correct

Subtask #4
47.0 / 47.0

#	결과	실행 시간	메모리	Grader output
1	Correct	16 ms	43424 KB	Output is correct
2	Correct	16 ms	43424 KB	Output is correct
3	Correct	19 ms	43424 KB	Output is correct
4	Correct	159 ms	43424 KB	Output is correct
5	Correct	516 ms	43424 KB	Output is correct
6	Correct	23 ms	43424 KB	Output is correct
7	Correct	266 ms	43424 KB	Output is correct
8	Correct	6 ms	43424 KB	Output is correct
9	Correct	6 ms	43424 KB	Output is correct
10	Correct	3 ms	43424 KB	Output is correct
11	Correct	3 ms	43424 KB	Output is correct
12	Correct	3 ms	43424 KB	Output is correct
13	Correct	0 ms	43424 KB	Output is correct
14	Correct	33 ms	43424 KB	Output is correct
15	Correct	13 ms	43424 KB	Output is correct
16	Correct	13 ms	43424 KB	Output is correct
17	Correct	0 ms	43424 KB	Output is correct
18	Correct	19 ms	43424 KB	Output is correct
19	Correct	106 ms	43424 KB	Output is correct
20	Correct	296 ms	43424 KB	Output is correct
21	Correct	26 ms	43424 KB	Output is correct
22	Correct	143 ms	43424 KB	Output is correct
23	Correct	13 ms	43424 KB	Output is correct
24	Correct	36 ms	43424 KB	Output is correct
25	Correct	299 ms	43424 KB	Output is correct
26	Correct	3 ms	43424 KB	Output is correct
27	Correct	0 ms	43424 KB	Output is correct
28	Correct	19 ms	43424 KB	Output is correct
29	Correct	3 ms	43424 KB	Output is correct
30	Correct	9 ms	43424 KB	Output is correct
31	Correct	16 ms	43424 KB	Output is correct
32	Correct	19 ms	43424 KB	Output is correct
33	Correct	76 ms	43424 KB	Output is correct
34	Correct	186 ms	43424 KB	Output is correct
35	Correct	13 ms	43424 KB	Output is correct
36	Correct	93 ms	43424 KB	Output is correct
37	Correct	3 ms	43424 KB	Output is correct
38	Correct	43 ms	43424 KB	Output is correct
39	Correct	3 ms	43424 KB	Output is correct
40	Correct	9 ms	43424 KB	Output is correct
41	Correct	6 ms	43424 KB	Output is correct
42	Correct	0 ms	43424 KB	Output is correct

답안 #39033

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