답안 #20485 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20485	2017-02-12T04:25:25 Z	Lower Boundary(#62, pica4500)	Can polan into space? (OJUZ11_space)	C++	11 / 100	1000 ms	10956 KB

space

#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;

int n;
bool visited[200001];
long long int cache[301][301];
struct choojin {
	int a[3];
	choojin(int _a, int _b, int _c) {
		a[0] = _a;
		a[1] = _b;
		a[2] = _c;
	}
};
vector<choojin> list;
vector<int> result;
int countNear(int cur) {
	int count = 0;
	for (int i = -1; i < 2; i++) {
		if (i == 0) continue;
		int pos = cur + i;
		if (pos >= 0 && pos < n) {
			if (visited[pos]) count++;
		}
	}
	return count;
}
long long int solve(int cur, int k) {
	if(k != 0) visited[cur] = true;
	if(k == n) return list[cur].a[countNear(cur)];
	long long int ret = 0;
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			long long int tmp = ret;
			if(k == 0) ret = max(ret, solve(i, k + 1));
			else ret = max(ret, list[cur].a[countNear(cur)] + solve(i, k + 1));
			if (tmp != ret) cache[cur][k] = i;
			visited[i] = false;
		}
	}
	return ret;
}

void reconstruct(int cur, int k) {
	if (k == n) return;
	result.push_back(cache[cur][k]);
	solve(cache[cur][k], k + 1);
	reconstruct(cache[cur][k], k + 1);
}

int main() {
	memset(cache, -1, sizeof(cache));
	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		list.push_back(choojin(a, b, c));
	}
	cout << solve(0, 0) << endl;
	reconstruct(0, 0);
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] + 1 << ' ';
	}
}

Compilation message

space.cpp: In function 'int main()':
space.cpp:64:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < result.size(); i++) {
                    ^

Subtask #1
11.0 / 11.0

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

Subtask #2
0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2924 KB	Output is correct
2	Correct	0 ms	2924 KB	Output is correct
3	Correct	3 ms	2924 KB	Output is correct
4	Correct	3 ms	2924 KB	Output is correct
5	Correct	0 ms	2924 KB	Output is correct
6	Correct	0 ms	2924 KB	Output is correct
7	Correct	0 ms	2924 KB	Output is correct
8	Correct	0 ms	2924 KB	Output is correct
9	Correct	3 ms	2924 KB	Output is correct
10	Correct	3 ms	2924 KB	Output is correct
11	Correct	3 ms	2924 KB	Output is correct
12	Correct	3 ms	2924 KB	Output is correct
13	Correct	3 ms	2924 KB	Output is correct
14	Correct	0 ms	2924 KB	Output is correct
15	Correct	3 ms	2924 KB	Output is correct
16	Correct	0 ms	2924 KB	Output is correct
17	Correct	3 ms	2924 KB	Output is correct
18	Correct	3 ms	2924 KB	Output is correct
19	Correct	0 ms	2924 KB	Output is correct
20	Correct	0 ms	2924 KB	Output is correct
21	Correct	0 ms	2924 KB	Output is correct
22	Correct	29 ms	2924 KB	Output is correct
23	Execution timed out	1000 ms	2924 KB	Execution timed out
24	Execution timed out	1000 ms	2924 KB	Execution timed out
25	Execution timed out	1000 ms	2924 KB	Execution timed out
26	Execution timed out	1000 ms	2924 KB	Execution timed out
27	Execution timed out	1000 ms	2924 KB	Execution timed out
28	Execution timed out	1000 ms	2924 KB	Execution timed out
29	Execution timed out	1000 ms	2924 KB	Execution timed out
30	Execution timed out	1000 ms	2924 KB	Execution timed out
31	Execution timed out	1000 ms	2924 KB	Execution timed out
32	Execution timed out	1000 ms	2924 KB	Execution timed out
33	Execution timed out	1000 ms	2924 KB	Execution timed out
34	Execution timed out	1000 ms	2924 KB	Execution timed out
35	Execution timed out	1000 ms	2924 KB	Execution timed out
36	Execution timed out	1000 ms	2924 KB	Execution timed out
37	Execution timed out	1000 ms	2924 KB	Execution timed out

Subtask #3
0 / 23.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2924 KB	Output is correct
2	Correct	0 ms	2924 KB	Output is correct
3	Correct	3 ms	2924 KB	Output is correct
4	Correct	3 ms	2924 KB	Output is correct
5	Correct	0 ms	2924 KB	Output is correct
6	Correct	0 ms	2924 KB	Output is correct
7	Correct	0 ms	2924 KB	Output is correct
8	Correct	0 ms	2924 KB	Output is correct
9	Correct	3 ms	2924 KB	Output is correct
10	Correct	3 ms	2924 KB	Output is correct
11	Correct	3 ms	2924 KB	Output is correct
12	Correct	3 ms	2924 KB	Output is correct
13	Correct	3 ms	2924 KB	Output is correct
14	Correct	0 ms	2924 KB	Output is correct
15	Correct	3 ms	2924 KB	Output is correct
16	Correct	0 ms	2924 KB	Output is correct
17	Correct	3 ms	2924 KB	Output is correct
18	Correct	3 ms	2924 KB	Output is correct
19	Correct	0 ms	2924 KB	Output is correct
20	Correct	0 ms	2924 KB	Output is correct
21	Correct	0 ms	2924 KB	Output is correct
22	Correct	29 ms	2924 KB	Output is correct
23	Execution timed out	1000 ms	2924 KB	Execution timed out
24	Execution timed out	1000 ms	2924 KB	Execution timed out
25	Execution timed out	1000 ms	2924 KB	Execution timed out
26	Execution timed out	1000 ms	2924 KB	Execution timed out
27	Execution timed out	1000 ms	2924 KB	Execution timed out
28	Execution timed out	1000 ms	2924 KB	Execution timed out
29	Execution timed out	1000 ms	2924 KB	Execution timed out
30	Execution timed out	1000 ms	2924 KB	Execution timed out
31	Execution timed out	1000 ms	2924 KB	Execution timed out
32	Execution timed out	1000 ms	2924 KB	Execution timed out
33	Execution timed out	1000 ms	2924 KB	Execution timed out
34	Execution timed out	1000 ms	2924 KB	Execution timed out
35	Execution timed out	1000 ms	2924 KB	Execution timed out
36	Execution timed out	1000 ms	2924 KB	Execution timed out
37	Execution timed out	1000 ms	2924 KB	Execution timed out
38	Execution timed out	1000 ms	2924 KB	Execution timed out
39	Execution timed out	1000 ms	2924 KB	Execution timed out
40	Execution timed out	1000 ms	2924 KB	Execution timed out
41	Execution timed out	1000 ms	2924 KB	Execution timed out
42	Execution timed out	1000 ms	2924 KB	Execution timed out
43	Execution timed out	1000 ms	2924 KB	Execution timed out
44	Execution timed out	1000 ms	2924 KB	Execution timed out
45	Execution timed out	1000 ms	2924 KB	Execution timed out
46	Execution timed out	1000 ms	2924 KB	Execution timed out
47	Execution timed out	1000 ms	2924 KB	Execution timed out
48	Execution timed out	1000 ms	2924 KB	Execution timed out
49	Execution timed out	1000 ms	2924 KB	Execution timed out
50	Execution timed out	1000 ms	2924 KB	Execution timed out
51	Execution timed out	1000 ms	2924 KB	Execution timed out
52	Execution timed out	1000 ms	2924 KB	Execution timed out
53	Execution timed out	1000 ms	2924 KB	Execution timed out

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2924 KB	Output is correct
2	Correct	0 ms	2924 KB	Output is correct
3	Correct	3 ms	2924 KB	Output is correct
4	Correct	3 ms	2924 KB	Output is correct
5	Correct	0 ms	2924 KB	Output is correct
6	Correct	0 ms	2924 KB	Output is correct
7	Correct	0 ms	2924 KB	Output is correct
8	Correct	0 ms	2924 KB	Output is correct
9	Correct	3 ms	2924 KB	Output is correct
10	Correct	3 ms	2924 KB	Output is correct
11	Correct	3 ms	2924 KB	Output is correct
12	Correct	3 ms	2924 KB	Output is correct
13	Correct	3 ms	2924 KB	Output is correct
14	Correct	0 ms	2924 KB	Output is correct
15	Correct	3 ms	2924 KB	Output is correct
16	Correct	0 ms	2924 KB	Output is correct
17	Correct	3 ms	2924 KB	Output is correct
18	Correct	3 ms	2924 KB	Output is correct
19	Correct	0 ms	2924 KB	Output is correct
20	Correct	0 ms	2924 KB	Output is correct
21	Correct	0 ms	2924 KB	Output is correct
22	Correct	29 ms	2924 KB	Output is correct
23	Execution timed out	1000 ms	2924 KB	Execution timed out
24	Execution timed out	1000 ms	2924 KB	Execution timed out
25	Execution timed out	1000 ms	2924 KB	Execution timed out
26	Execution timed out	1000 ms	2924 KB	Execution timed out
27	Execution timed out	1000 ms	2924 KB	Execution timed out
28	Execution timed out	1000 ms	2924 KB	Execution timed out
29	Execution timed out	1000 ms	2924 KB	Execution timed out
30	Execution timed out	1000 ms	2924 KB	Execution timed out
31	Execution timed out	1000 ms	2924 KB	Execution timed out
32	Execution timed out	1000 ms	2924 KB	Execution timed out
33	Execution timed out	1000 ms	2924 KB	Execution timed out
34	Execution timed out	1000 ms	2924 KB	Execution timed out
35	Execution timed out	1000 ms	2924 KB	Execution timed out
36	Execution timed out	1000 ms	2924 KB	Execution timed out
37	Execution timed out	1000 ms	2924 KB	Execution timed out
38	Execution timed out	1000 ms	2924 KB	Execution timed out
39	Execution timed out	1000 ms	2924 KB	Execution timed out
40	Execution timed out	1000 ms	2924 KB	Execution timed out
41	Execution timed out	1000 ms	2924 KB	Execution timed out
42	Execution timed out	1000 ms	2924 KB	Execution timed out
43	Execution timed out	1000 ms	2924 KB	Execution timed out
44	Execution timed out	1000 ms	2924 KB	Execution timed out
45	Execution timed out	1000 ms	2924 KB	Execution timed out
46	Execution timed out	1000 ms	2924 KB	Execution timed out
47	Execution timed out	1000 ms	2924 KB	Execution timed out
48	Execution timed out	1000 ms	2924 KB	Execution timed out
49	Execution timed out	1000 ms	2924 KB	Execution timed out
50	Execution timed out	1000 ms	2924 KB	Execution timed out
51	Execution timed out	1000 ms	2924 KB	Execution timed out
52	Execution timed out	1000 ms	2924 KB	Execution timed out
53	Execution timed out	1000 ms	2924 KB	Execution timed out
54	Execution timed out	1000 ms	2924 KB	Execution timed out
55	Runtime error	56 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	56 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	59 ms	3848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	59 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	59 ms	3856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	56 ms	3856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	59 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	33 ms	3532 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	0 ms	2952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	56 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	49 ms	3848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	59 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	19 ms	3352 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	9 ms	3216 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	56 ms	3848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #5
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2924 KB	Output is correct
2	Correct	0 ms	2924 KB	Output is correct
3	Correct	3 ms	2924 KB	Output is correct
4	Correct	3 ms	2924 KB	Output is correct
5	Correct	0 ms	2924 KB	Output is correct
6	Correct	0 ms	2924 KB	Output is correct
7	Correct	0 ms	2924 KB	Output is correct
8	Correct	0 ms	2924 KB	Output is correct
9	Correct	3 ms	2924 KB	Output is correct
10	Correct	3 ms	2924 KB	Output is correct
11	Correct	3 ms	2924 KB	Output is correct
12	Correct	3 ms	2924 KB	Output is correct
13	Correct	3 ms	2924 KB	Output is correct
14	Correct	0 ms	2924 KB	Output is correct
15	Correct	3 ms	2924 KB	Output is correct
16	Correct	0 ms	2924 KB	Output is correct
17	Correct	3 ms	2924 KB	Output is correct
18	Correct	3 ms	2924 KB	Output is correct
19	Correct	0 ms	2924 KB	Output is correct
20	Correct	0 ms	2924 KB	Output is correct
21	Correct	0 ms	2924 KB	Output is correct
22	Correct	29 ms	2924 KB	Output is correct
23	Execution timed out	1000 ms	2924 KB	Execution timed out
24	Execution timed out	1000 ms	2924 KB	Execution timed out
25	Execution timed out	1000 ms	2924 KB	Execution timed out
26	Execution timed out	1000 ms	2924 KB	Execution timed out
27	Execution timed out	1000 ms	2924 KB	Execution timed out
28	Execution timed out	1000 ms	2924 KB	Execution timed out
29	Execution timed out	1000 ms	2924 KB	Execution timed out
30	Execution timed out	1000 ms	2924 KB	Execution timed out
31	Execution timed out	1000 ms	2924 KB	Execution timed out
32	Execution timed out	1000 ms	2924 KB	Execution timed out
33	Execution timed out	1000 ms	2924 KB	Execution timed out
34	Execution timed out	1000 ms	2924 KB	Execution timed out
35	Execution timed out	1000 ms	2924 KB	Execution timed out
36	Execution timed out	1000 ms	2924 KB	Execution timed out
37	Execution timed out	1000 ms	2924 KB	Execution timed out
38	Execution timed out	1000 ms	2924 KB	Execution timed out
39	Execution timed out	1000 ms	2924 KB	Execution timed out
40	Execution timed out	1000 ms	2924 KB	Execution timed out
41	Execution timed out	1000 ms	2924 KB	Execution timed out
42	Execution timed out	1000 ms	2924 KB	Execution timed out
43	Execution timed out	1000 ms	2924 KB	Execution timed out
44	Execution timed out	1000 ms	2924 KB	Execution timed out
45	Execution timed out	1000 ms	2924 KB	Execution timed out
46	Execution timed out	1000 ms	2924 KB	Execution timed out
47	Execution timed out	1000 ms	2924 KB	Execution timed out
48	Execution timed out	1000 ms	2924 KB	Execution timed out
49	Execution timed out	1000 ms	2924 KB	Execution timed out
50	Execution timed out	1000 ms	2924 KB	Execution timed out
51	Execution timed out	1000 ms	2924 KB	Execution timed out
52	Execution timed out	1000 ms	2924 KB	Execution timed out
53	Execution timed out	1000 ms	2924 KB	Execution timed out
54	Execution timed out	1000 ms	2924 KB	Execution timed out
55	Runtime error	56 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
56	Runtime error	56 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
57	Runtime error	59 ms	3848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
58	Runtime error	59 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
59	Runtime error	59 ms	3856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
60	Runtime error	56 ms	3856 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
61	Runtime error	59 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
62	Runtime error	33 ms	3532 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
63	Runtime error	0 ms	2952 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
64	Runtime error	56 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
65	Runtime error	49 ms	3848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
66	Runtime error	59 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
67	Runtime error	19 ms	3352 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
68	Runtime error	9 ms	3216 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
69	Runtime error	56 ms	3848 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
70	Execution timed out	1000 ms	3856 KB	Execution timed out
71	Execution timed out	1000 ms	10784 KB	Execution timed out
72	Execution timed out	1000 ms	10864 KB	Execution timed out
73	Execution timed out	1000 ms	10780 KB	Execution timed out
74	Execution timed out	1000 ms	10956 KB	Execution timed out
75	Execution timed out	1000 ms	10820 KB	Execution timed out
76	Execution timed out	1000 ms	10860 KB	Execution timed out
77	Execution timed out	1000 ms	9512 KB	Execution timed out
78	Execution timed out	1000 ms	10756 KB	Execution timed out
79	Execution timed out	1000 ms	10756 KB	Execution timed out
80	Execution timed out	1000 ms	10800 KB	Execution timed out
81	Runtime error	779 ms	6768 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
82	Execution timed out	1000 ms	10928 KB	Execution timed out
83	Execution timed out	1000 ms	10684 KB	Execution timed out
84	Execution timed out	1000 ms	10800 KB	Execution timed out
85	Execution timed out	1000 ms	10784 KB	Execution timed out
86	Execution timed out	1000 ms	10832 KB	Execution timed out
87	Execution timed out	1000 ms	10776 KB	Execution timed out
88	Runtime error	499 ms	5756 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
89	Execution timed out	1000 ms	9444 KB	Execution timed out
90	Execution timed out	1000 ms	9580 KB	Execution timed out
91	Runtime error	49 ms	3852 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
92	Execution timed out	1000 ms	9564 KB	Execution timed out

답안 #20485

Compilation message

Subtask #1 11.0 / 11.0

Subtask #2 0 / 12.0

Subtask #3 0 / 23.0

Subtask #4 0 / 26.0

Subtask #5 0 / 28.0

Subtask #1
11.0 / 11.0

Subtask #2
0 / 12.0

Subtask #3
0 / 23.0

Subtask #4
0 / 26.0

Subtask #5
0 / 28.0