# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
66199 | 2018-08-10T04:25:26 Z | 강태규(#1885) | Can polan into space? (OJUZ11_space) | C++11 | 233 ms | 19388 KB |
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_map> #include <functional> #include <cstring> #include <cmath> #include <ctime> #include <cstdlib> using namespace std; typedef long long llong; typedef long double ld; typedef pair<int, int> pii; typedef pair<llong, llong> pll; const llong inf = 1e17; int pr[200001][2][2]; llong dp[200001][2][2]; int a[200001][3]; int st[200001]; int ord[200000]; int main() { int n; scanf("%d", &n); for (int i = 1; i <= n; ++i) { for (int j = 0; j < 3; ++j) { scanf("%d", a[i] + j); } } dp[0][0][0] = dp[0][1][0] = -inf; for (int i = 1; i <= n; ++i) { for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { for (int p = 0; p < 2; ++p) { llong d = dp[i - 1][j][k] + a[i][(k ^ 1) + p]; if (dp[i][k][p] < d) { dp[i][k][p] = d; pr[i][k][p] = j; } } } } } llong ans = dp[n][0][0]; int p = 0, q = 0; if (ans < dp[n][1][0]) { ans = dp[n][1][0]; p = 1; } printf("%lld\n", ans); int mx = 0, mn = 0; for (int i = n; --i; ) { int t = pr[i + 1][p][q]; if (p) st[i] = ++mx; else st[i] = --mn; q = p; p = t; } for (int i = 1; i <= n; ++i) { ord[st[i] - mn] = i; } for (int i = 0; i < n; ++i) { printf("%d%c", ord[i], "\n "[i + 1 < n]); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 484 KB | Output is correct |
3 | Correct | 3 ms | 484 KB | Output is correct |
4 | Correct | 4 ms | 484 KB | Output is correct |
5 | Correct | 3 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 484 KB | Output is correct |
7 | Correct | 3 ms | 524 KB | Output is correct |
8 | Correct | 3 ms | 572 KB | Output is correct |
9 | Correct | 3 ms | 624 KB | Output is correct |
10 | Correct | 4 ms | 628 KB | Output is correct |
11 | Correct | 4 ms | 648 KB | Output is correct |
12 | Correct | 3 ms | 656 KB | Output is correct |
13 | Correct | 1 ms | 660 KB | Output is correct |
14 | Correct | 3 ms | 672 KB | Output is correct |
15 | Correct | 4 ms | 680 KB | Output is correct |
16 | Correct | 3 ms | 680 KB | Output is correct |
17 | Correct | 2 ms | 680 KB | Output is correct |
18 | Correct | 3 ms | 688 KB | Output is correct |
19 | Correct | 3 ms | 692 KB | Output is correct |
20 | Correct | 3 ms | 696 KB | Output is correct |
21 | Correct | 3 ms | 700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 484 KB | Output is correct |
3 | Correct | 3 ms | 484 KB | Output is correct |
4 | Correct | 4 ms | 484 KB | Output is correct |
5 | Correct | 3 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 484 KB | Output is correct |
7 | Correct | 3 ms | 524 KB | Output is correct |
8 | Correct | 3 ms | 572 KB | Output is correct |
9 | Correct | 3 ms | 624 KB | Output is correct |
10 | Correct | 4 ms | 628 KB | Output is correct |
11 | Correct | 4 ms | 648 KB | Output is correct |
12 | Correct | 3 ms | 656 KB | Output is correct |
13 | Correct | 1 ms | 660 KB | Output is correct |
14 | Correct | 3 ms | 672 KB | Output is correct |
15 | Correct | 4 ms | 680 KB | Output is correct |
16 | Correct | 3 ms | 680 KB | Output is correct |
17 | Correct | 2 ms | 680 KB | Output is correct |
18 | Correct | 3 ms | 688 KB | Output is correct |
19 | Correct | 3 ms | 692 KB | Output is correct |
20 | Correct | 3 ms | 696 KB | Output is correct |
21 | Correct | 3 ms | 700 KB | Output is correct |
22 | Correct | 4 ms | 704 KB | Output is correct |
23 | Correct | 4 ms | 708 KB | Output is correct |
24 | Correct | 3 ms | 708 KB | Output is correct |
25 | Correct | 3 ms | 716 KB | Output is correct |
26 | Correct | 3 ms | 720 KB | Output is correct |
27 | Correct | 3 ms | 724 KB | Output is correct |
28 | Correct | 3 ms | 728 KB | Output is correct |
29 | Correct | 3 ms | 732 KB | Output is correct |
30 | Correct | 3 ms | 740 KB | Output is correct |
31 | Correct | 3 ms | 740 KB | Output is correct |
32 | Correct | 4 ms | 744 KB | Output is correct |
33 | Correct | 3 ms | 748 KB | Output is correct |
34 | Correct | 7 ms | 748 KB | Output is correct |
35 | Correct | 4 ms | 748 KB | Output is correct |
36 | Correct | 3 ms | 760 KB | Output is correct |
37 | Correct | 2 ms | 764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 484 KB | Output is correct |
3 | Correct | 3 ms | 484 KB | Output is correct |
4 | Correct | 4 ms | 484 KB | Output is correct |
5 | Correct | 3 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 484 KB | Output is correct |
7 | Correct | 3 ms | 524 KB | Output is correct |
8 | Correct | 3 ms | 572 KB | Output is correct |
9 | Correct | 3 ms | 624 KB | Output is correct |
10 | Correct | 4 ms | 628 KB | Output is correct |
11 | Correct | 4 ms | 648 KB | Output is correct |
12 | Correct | 3 ms | 656 KB | Output is correct |
13 | Correct | 1 ms | 660 KB | Output is correct |
14 | Correct | 3 ms | 672 KB | Output is correct |
15 | Correct | 4 ms | 680 KB | Output is correct |
16 | Correct | 3 ms | 680 KB | Output is correct |
17 | Correct | 2 ms | 680 KB | Output is correct |
18 | Correct | 3 ms | 688 KB | Output is correct |
19 | Correct | 3 ms | 692 KB | Output is correct |
20 | Correct | 3 ms | 696 KB | Output is correct |
21 | Correct | 3 ms | 700 KB | Output is correct |
22 | Correct | 4 ms | 704 KB | Output is correct |
23 | Correct | 4 ms | 708 KB | Output is correct |
24 | Correct | 3 ms | 708 KB | Output is correct |
25 | Correct | 3 ms | 716 KB | Output is correct |
26 | Correct | 3 ms | 720 KB | Output is correct |
27 | Correct | 3 ms | 724 KB | Output is correct |
28 | Correct | 3 ms | 728 KB | Output is correct |
29 | Correct | 3 ms | 732 KB | Output is correct |
30 | Correct | 3 ms | 740 KB | Output is correct |
31 | Correct | 3 ms | 740 KB | Output is correct |
32 | Correct | 4 ms | 744 KB | Output is correct |
33 | Correct | 3 ms | 748 KB | Output is correct |
34 | Correct | 7 ms | 748 KB | Output is correct |
35 | Correct | 4 ms | 748 KB | Output is correct |
36 | Correct | 3 ms | 760 KB | Output is correct |
37 | Correct | 2 ms | 764 KB | Output is correct |
38 | Correct | 4 ms | 768 KB | Output is correct |
39 | Correct | 6 ms | 772 KB | Output is correct |
40 | Correct | 3 ms | 848 KB | Output is correct |
41 | Correct | 3 ms | 848 KB | Output is correct |
42 | Correct | 3 ms | 848 KB | Output is correct |
43 | Correct | 4 ms | 848 KB | Output is correct |
44 | Correct | 3 ms | 848 KB | Output is correct |
45 | Correct | 4 ms | 848 KB | Output is correct |
46 | Correct | 4 ms | 852 KB | Output is correct |
47 | Correct | 4 ms | 860 KB | Output is correct |
48 | Correct | 4 ms | 872 KB | Output is correct |
49 | Correct | 4 ms | 964 KB | Output is correct |
50 | Correct | 3 ms | 976 KB | Output is correct |
51 | Correct | 3 ms | 976 KB | Output is correct |
52 | Correct | 4 ms | 976 KB | Output is correct |
53 | Correct | 2 ms | 976 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 484 KB | Output is correct |
3 | Correct | 3 ms | 484 KB | Output is correct |
4 | Correct | 4 ms | 484 KB | Output is correct |
5 | Correct | 3 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 484 KB | Output is correct |
7 | Correct | 3 ms | 524 KB | Output is correct |
8 | Correct | 3 ms | 572 KB | Output is correct |
9 | Correct | 3 ms | 624 KB | Output is correct |
10 | Correct | 4 ms | 628 KB | Output is correct |
11 | Correct | 4 ms | 648 KB | Output is correct |
12 | Correct | 3 ms | 656 KB | Output is correct |
13 | Correct | 1 ms | 660 KB | Output is correct |
14 | Correct | 3 ms | 672 KB | Output is correct |
15 | Correct | 4 ms | 680 KB | Output is correct |
16 | Correct | 3 ms | 680 KB | Output is correct |
17 | Correct | 2 ms | 680 KB | Output is correct |
18 | Correct | 3 ms | 688 KB | Output is correct |
19 | Correct | 3 ms | 692 KB | Output is correct |
20 | Correct | 3 ms | 696 KB | Output is correct |
21 | Correct | 3 ms | 700 KB | Output is correct |
22 | Correct | 4 ms | 704 KB | Output is correct |
23 | Correct | 4 ms | 708 KB | Output is correct |
24 | Correct | 3 ms | 708 KB | Output is correct |
25 | Correct | 3 ms | 716 KB | Output is correct |
26 | Correct | 3 ms | 720 KB | Output is correct |
27 | Correct | 3 ms | 724 KB | Output is correct |
28 | Correct | 3 ms | 728 KB | Output is correct |
29 | Correct | 3 ms | 732 KB | Output is correct |
30 | Correct | 3 ms | 740 KB | Output is correct |
31 | Correct | 3 ms | 740 KB | Output is correct |
32 | Correct | 4 ms | 744 KB | Output is correct |
33 | Correct | 3 ms | 748 KB | Output is correct |
34 | Correct | 7 ms | 748 KB | Output is correct |
35 | Correct | 4 ms | 748 KB | Output is correct |
36 | Correct | 3 ms | 760 KB | Output is correct |
37 | Correct | 2 ms | 764 KB | Output is correct |
38 | Correct | 4 ms | 768 KB | Output is correct |
39 | Correct | 6 ms | 772 KB | Output is correct |
40 | Correct | 3 ms | 848 KB | Output is correct |
41 | Correct | 3 ms | 848 KB | Output is correct |
42 | Correct | 3 ms | 848 KB | Output is correct |
43 | Correct | 4 ms | 848 KB | Output is correct |
44 | Correct | 3 ms | 848 KB | Output is correct |
45 | Correct | 4 ms | 848 KB | Output is correct |
46 | Correct | 4 ms | 852 KB | Output is correct |
47 | Correct | 4 ms | 860 KB | Output is correct |
48 | Correct | 4 ms | 872 KB | Output is correct |
49 | Correct | 4 ms | 964 KB | Output is correct |
50 | Correct | 3 ms | 976 KB | Output is correct |
51 | Correct | 3 ms | 976 KB | Output is correct |
52 | Correct | 4 ms | 976 KB | Output is correct |
53 | Correct | 2 ms | 976 KB | Output is correct |
54 | Correct | 3 ms | 976 KB | Output is correct |
55 | Correct | 13 ms | 1848 KB | Output is correct |
56 | Correct | 18 ms | 2264 KB | Output is correct |
57 | Correct | 12 ms | 2572 KB | Output is correct |
58 | Correct | 14 ms | 2832 KB | Output is correct |
59 | Correct | 14 ms | 3132 KB | Output is correct |
60 | Correct | 13 ms | 3464 KB | Output is correct |
61 | Correct | 12 ms | 3772 KB | Output is correct |
62 | Correct | 10 ms | 3772 KB | Output is correct |
63 | Correct | 5 ms | 3772 KB | Output is correct |
64 | Correct | 16 ms | 4304 KB | Output is correct |
65 | Correct | 11 ms | 4400 KB | Output is correct |
66 | Correct | 14 ms | 4700 KB | Output is correct |
67 | Correct | 11 ms | 4700 KB | Output is correct |
68 | Correct | 7 ms | 4700 KB | Output is correct |
69 | Correct | 12 ms | 5208 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 376 KB | Output is correct |
2 | Correct | 4 ms | 484 KB | Output is correct |
3 | Correct | 3 ms | 484 KB | Output is correct |
4 | Correct | 4 ms | 484 KB | Output is correct |
5 | Correct | 3 ms | 484 KB | Output is correct |
6 | Correct | 3 ms | 484 KB | Output is correct |
7 | Correct | 3 ms | 524 KB | Output is correct |
8 | Correct | 3 ms | 572 KB | Output is correct |
9 | Correct | 3 ms | 624 KB | Output is correct |
10 | Correct | 4 ms | 628 KB | Output is correct |
11 | Correct | 4 ms | 648 KB | Output is correct |
12 | Correct | 3 ms | 656 KB | Output is correct |
13 | Correct | 1 ms | 660 KB | Output is correct |
14 | Correct | 3 ms | 672 KB | Output is correct |
15 | Correct | 4 ms | 680 KB | Output is correct |
16 | Correct | 3 ms | 680 KB | Output is correct |
17 | Correct | 2 ms | 680 KB | Output is correct |
18 | Correct | 3 ms | 688 KB | Output is correct |
19 | Correct | 3 ms | 692 KB | Output is correct |
20 | Correct | 3 ms | 696 KB | Output is correct |
21 | Correct | 3 ms | 700 KB | Output is correct |
22 | Correct | 4 ms | 704 KB | Output is correct |
23 | Correct | 4 ms | 708 KB | Output is correct |
24 | Correct | 3 ms | 708 KB | Output is correct |
25 | Correct | 3 ms | 716 KB | Output is correct |
26 | Correct | 3 ms | 720 KB | Output is correct |
27 | Correct | 3 ms | 724 KB | Output is correct |
28 | Correct | 3 ms | 728 KB | Output is correct |
29 | Correct | 3 ms | 732 KB | Output is correct |
30 | Correct | 3 ms | 740 KB | Output is correct |
31 | Correct | 3 ms | 740 KB | Output is correct |
32 | Correct | 4 ms | 744 KB | Output is correct |
33 | Correct | 3 ms | 748 KB | Output is correct |
34 | Correct | 7 ms | 748 KB | Output is correct |
35 | Correct | 4 ms | 748 KB | Output is correct |
36 | Correct | 3 ms | 760 KB | Output is correct |
37 | Correct | 2 ms | 764 KB | Output is correct |
38 | Correct | 4 ms | 768 KB | Output is correct |
39 | Correct | 6 ms | 772 KB | Output is correct |
40 | Correct | 3 ms | 848 KB | Output is correct |
41 | Correct | 3 ms | 848 KB | Output is correct |
42 | Correct | 3 ms | 848 KB | Output is correct |
43 | Correct | 4 ms | 848 KB | Output is correct |
44 | Correct | 3 ms | 848 KB | Output is correct |
45 | Correct | 4 ms | 848 KB | Output is correct |
46 | Correct | 4 ms | 852 KB | Output is correct |
47 | Correct | 4 ms | 860 KB | Output is correct |
48 | Correct | 4 ms | 872 KB | Output is correct |
49 | Correct | 4 ms | 964 KB | Output is correct |
50 | Correct | 3 ms | 976 KB | Output is correct |
51 | Correct | 3 ms | 976 KB | Output is correct |
52 | Correct | 4 ms | 976 KB | Output is correct |
53 | Correct | 2 ms | 976 KB | Output is correct |
54 | Correct | 3 ms | 976 KB | Output is correct |
55 | Correct | 13 ms | 1848 KB | Output is correct |
56 | Correct | 18 ms | 2264 KB | Output is correct |
57 | Correct | 12 ms | 2572 KB | Output is correct |
58 | Correct | 14 ms | 2832 KB | Output is correct |
59 | Correct | 14 ms | 3132 KB | Output is correct |
60 | Correct | 13 ms | 3464 KB | Output is correct |
61 | Correct | 12 ms | 3772 KB | Output is correct |
62 | Correct | 10 ms | 3772 KB | Output is correct |
63 | Correct | 5 ms | 3772 KB | Output is correct |
64 | Correct | 16 ms | 4304 KB | Output is correct |
65 | Correct | 11 ms | 4400 KB | Output is correct |
66 | Correct | 14 ms | 4700 KB | Output is correct |
67 | Correct | 11 ms | 4700 KB | Output is correct |
68 | Correct | 7 ms | 4700 KB | Output is correct |
69 | Correct | 12 ms | 5208 KB | Output is correct |
70 | Correct | 14 ms | 5508 KB | Output is correct |
71 | Correct | 190 ms | 19260 KB | Output is correct |
72 | Correct | 167 ms | 19388 KB | Output is correct |
73 | Correct | 183 ms | 19388 KB | Output is correct |
74 | Correct | 157 ms | 19388 KB | Output is correct |
75 | Correct | 184 ms | 19388 KB | Output is correct |
76 | Correct | 186 ms | 19388 KB | Output is correct |
77 | Correct | 76 ms | 19388 KB | Output is correct |
78 | Correct | 194 ms | 19388 KB | Output is correct |
79 | Correct | 186 ms | 19388 KB | Output is correct |
80 | Correct | 200 ms | 19388 KB | Output is correct |
81 | Correct | 39 ms | 19388 KB | Output is correct |
82 | Correct | 131 ms | 19388 KB | Output is correct |
83 | Correct | 185 ms | 19388 KB | Output is correct |
84 | Correct | 190 ms | 19388 KB | Output is correct |
85 | Correct | 219 ms | 19388 KB | Output is correct |
86 | Correct | 233 ms | 19388 KB | Output is correct |
87 | Correct | 195 ms | 19388 KB | Output is correct |
88 | Correct | 33 ms | 19388 KB | Output is correct |
89 | Correct | 121 ms | 19388 KB | Output is correct |
90 | Correct | 81 ms | 19388 KB | Output is correct |
91 | Correct | 10 ms | 19388 KB | Output is correct |
92 | Correct | 71 ms | 19388 KB | Output is correct |