Submission #20485

# Submission time Handle Problem Language Result Execution time Memory
20485 2017-02-12T04:25:25 Z Lower Boundary(#62, pica4500) Can polan into space? (OJUZ11_space) C++
11 / 100
1000 ms 10956 KB
#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++) {
                    ^
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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
# Verdict Execution time Memory 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)
# Verdict Execution time Memory 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