답안 #54612 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
54612	2018-07-04T08:04:18 Z	aome	선물상자 (IOI15_boxes)	C++17	100 / 100	473 ms	167296 KB

boxes

#include "boxes.h"

#include <bits/stdc++.h>

using namespace std;

const int M = 10000005;
const long long INF = 1e18;

int arr[2][M];
long long f[2][M], g[M];

long long delivery(int N, int K, int L, int p[]) {
	int pos = -1;
	for (int i = 0; i < N; ++i) if (p[i] * 2 <= L) pos = i;
	int sz[2];
	sz[0] = 0;
	for (int i = 0; i <= pos; ++i) arr[0][++sz[0]] = p[i] * 2;
	sz[1] = 0;
	for (int i = N - 1; i > pos; --i) arr[1][++sz[1]] = (L - p[i]) * 2;
	for (int i = 0; i < 2; ++i) {
		for (int j = 1; j <= sz[i]; ++j) {
			if (j < K) f[i][j] = arr[i][j];
			else f[i][j] = f[i][j - K] + arr[i][j];
		}
	}
	for (int i = 0; i <= K; ++i) g[i] = INF;
	for (int i = sz[0]; i >= 0; --i) {
		if (sz[0] - i > K) break;
		g[sz[0] - i] = f[0][i];
	}
	long long res = INF;
	res = min(res, f[0][sz[0]] + f[1][sz[1]]);
	for (int i = sz[1]; i >= 0; --i) {
		if (sz[1] - i > K) break;
		res = min(res, g[K - (sz[1] - i)] + f[1][i] + L);
	}
	return res;
}

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	380 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	380 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	2 ms	420 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	404 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	380 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	2 ms	420 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	404 KB	Output is correct
33	Correct	48 ms	22076 KB	Output is correct
34	Correct	20 ms	17936 KB	Output is correct
35	Correct	23 ms	18380 KB	Output is correct
36	Correct	51 ms	24036 KB	Output is correct
37	Correct	47 ms	22924 KB	Output is correct
38	Correct	47 ms	22904 KB	Output is correct
39	Correct	44 ms	23120 KB	Output is correct
40	Correct	28 ms	19660 KB	Output is correct
41	Correct	49 ms	22936 KB	Output is correct
42	Correct	29 ms	19924 KB	Output is correct

Subtask #6
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	380 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	376 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	376 KB	Output is correct
18	Correct	2 ms	376 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	380 KB	Output is correct
21	Correct	2 ms	376 KB	Output is correct
22	Correct	2 ms	376 KB	Output is correct
23	Correct	2 ms	376 KB	Output is correct
24	Correct	2 ms	376 KB	Output is correct
25	Correct	2 ms	376 KB	Output is correct
26	Correct	2 ms	376 KB	Output is correct
27	Correct	2 ms	376 KB	Output is correct
28	Correct	2 ms	376 KB	Output is correct
29	Correct	2 ms	376 KB	Output is correct
30	Correct	2 ms	420 KB	Output is correct
31	Correct	2 ms	376 KB	Output is correct
32	Correct	2 ms	404 KB	Output is correct
33	Correct	48 ms	22076 KB	Output is correct
34	Correct	20 ms	17936 KB	Output is correct
35	Correct	23 ms	18380 KB	Output is correct
36	Correct	51 ms	24036 KB	Output is correct
37	Correct	47 ms	22924 KB	Output is correct
38	Correct	47 ms	22904 KB	Output is correct
39	Correct	44 ms	23120 KB	Output is correct
40	Correct	28 ms	19660 KB	Output is correct
41	Correct	49 ms	22936 KB	Output is correct
42	Correct	29 ms	19924 KB	Output is correct
43	Correct	473 ms	167296 KB	Output is correct
44	Correct	215 ms	161368 KB	Output is correct
45	Correct	235 ms	157624 KB	Output is correct
46	Correct	463 ms	163656 KB	Output is correct
47	Correct	434 ms	161188 KB	Output is correct
48	Correct	451 ms	159540 KB	Output is correct
49	Correct	405 ms	167032 KB	Output is correct
50	Correct	251 ms	161852 KB	Output is correct
51	Correct	454 ms	161604 KB	Output is correct
52	Correct	259 ms	160864 KB	Output is correct

답안 #54612

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 10.0 / 10.0

Subtask #3 15.0 / 15.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #6 30.0 / 30.0

Subtask #1
10.0 / 10.0

Subtask #2
10.0 / 10.0

Subtask #3
15.0 / 15.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0

Subtask #6
30.0 / 30.0