Submission #20497

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20497	2017-02-12T06:43:26 Z	안녕하세요 투어리스트입니다 진짜에요(#49, Namnamseo)	Can polan into space? (OJUZ11_space)	C++14	0 / 100	159 ms	16904 KB

space

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back

int n;
ll a[200010];
ll b[200010];
ll c[200010];

ll inf = (1LL<<60);

void shift(int x){
	c[x]=b[x]; b[x]=a[x]; a[x]=-inf;
}

ll dp[200010][4];

int use[200010];

#define NOA 0
#define HEA 1
#define AFA 2
#define HEC 3

int main()
{
	//freopen("in", "r", stdin);
    read(n); for(int i=1; i<=n; ++i) read(a[i], b[i], c[i]);
    dp[0][NOA] = 0;
    dp[0][HEA] = -inf;
    dp[0][AFA] = -inf;
    dp[0][HEC] = -inf;
    
    for(int i=1; i<=n; ++i){
		dp[i][NOA] = max(dp[i-1][HEC], dp[i-1][NOA]) + b[i];
		dp[i][HEA] = max(dp[i-1][HEC], dp[i-1][NOA]) + a[i];
		dp[i][AFA] = max(dp[i-1][AFA], dp[i-1][HEA]) + b[i];
		dp[i][HEC] = max(dp[i-1][AFA], dp[i-1][HEA]) + c[i];
    }
    
    ll ans = max(dp[n][AFA], dp[n][HEA]);
    printf("%lld\n", ans);
    int mi=0;
    if(ans == dp[n][AFA]) mi=AFA; else mi=HEA;
    for(int i=n; 1<=i; --i){
		if(mi == NOA){
			use[i]=2;
			mi = (dp[i-1][HEC] > dp[i-1][NOA] ? HEC : NOA);
		} else if(mi == HEA){
			use[i]=1;
			mi = (dp[i-1][HEC] > dp[i-1][NOA] ? HEC : NOA);
		} else if(mi == AFA){
			use[i]=1;
			mi = (dp[i-1][HEA] > dp[i-1][AFA] ? HEA : AFA);
		} else if(mi == HEC){
			use[i]=3;
			mi = (dp[i-1][HEA] > dp[i-1][AFA] ? HEA : AFA);
		}
    }
    
    vector<pp> av;
    for(int i=1; i<=n; ++i) av.pb({use[i], i});
    sort(all(av)); for(auto x:av) printf("%d ", x.second);
    return 0;
}

Compilation message

space.cpp: In function 'void read(int&)':
space.cpp:5:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^
space.cpp: In function 'void read(ll&)':
space.cpp:6:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                                   ^

Subtask #1
0 / 11.0

#	Verdict	Memory	Grader output
1	Correct	13744 KB	Output is correct
2	Incorrect	13744 KB	Output isn't correct
3	Incorrect	13744 KB	Output isn't correct
4	Correct	13744 KB	Output is correct
5	Correct	13744 KB	Output is correct
6	Correct	13744 KB	Output is correct
7	Correct	13744 KB	Output is correct
8	Incorrect	13744 KB	Output isn't correct
9	Correct	13744 KB	Output is correct
10	Incorrect	13744 KB	Output isn't correct
11	Correct	13744 KB	Output is correct
12	Correct	13744 KB	Output is correct
13	Correct	13744 KB	Output is correct
14	Incorrect	13744 KB	Output isn't correct
15	Correct	13744 KB	Output is correct
16	Incorrect	13744 KB	Output isn't correct
17	Correct	13744 KB	Output is correct
18	Incorrect	13744 KB	Output isn't correct
19	Correct	13744 KB	Output is correct
20	Incorrect	13744 KB	Output isn't correct
21	Correct	13744 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	13744 KB	Output is correct
2	Incorrect	13744 KB	Output isn't correct
3	Incorrect	13744 KB	Output isn't correct
4	Correct	13744 KB	Output is correct
5	Correct	13744 KB	Output is correct
6	Correct	13744 KB	Output is correct
7	Correct	13744 KB	Output is correct
8	Incorrect	13744 KB	Output isn't correct
9	Correct	13744 KB	Output is correct
10	Incorrect	13744 KB	Output isn't correct
11	Correct	13744 KB	Output is correct
12	Correct	13744 KB	Output is correct
13	Correct	13744 KB	Output is correct
14	Incorrect	13744 KB	Output isn't correct
15	Correct	13744 KB	Output is correct
16	Incorrect	13744 KB	Output isn't correct
17	Correct	13744 KB	Output is correct
18	Incorrect	13744 KB	Output isn't correct
19	Correct	13744 KB	Output is correct
20	Incorrect	13744 KB	Output isn't correct
21	Correct	13744 KB	Output is correct
22	Incorrect	13744 KB	Output isn't correct
23	Correct	13744 KB	Output is correct
24	Correct	13744 KB	Output is correct
25	Incorrect	13744 KB	Output isn't correct
26	Incorrect	13744 KB	Output isn't correct
27	Incorrect	13744 KB	Output isn't correct
28	Incorrect	13744 KB	Output isn't correct
29	Incorrect	13744 KB	Output isn't correct
30	Correct	13744 KB	Output is correct
31	Correct	13744 KB	Output is correct
32	Correct	13744 KB	Output is correct
33	Incorrect	13744 KB	Output isn't correct
34	Incorrect	13744 KB	Output isn't correct
35	Incorrect	13744 KB	Output isn't correct
36	Correct	13744 KB	Output is correct
37	Incorrect	13744 KB	Output isn't correct

Subtask #3
0 / 23.0

#	Verdict	Memory	Grader output
1	Correct	13744 KB	Output is correct
2	Incorrect	13744 KB	Output isn't correct
3	Incorrect	13744 KB	Output isn't correct
4	Correct	13744 KB	Output is correct
5	Correct	13744 KB	Output is correct
6	Correct	13744 KB	Output is correct
7	Correct	13744 KB	Output is correct
8	Incorrect	13744 KB	Output isn't correct
9	Correct	13744 KB	Output is correct
10	Incorrect	13744 KB	Output isn't correct
11	Correct	13744 KB	Output is correct
12	Correct	13744 KB	Output is correct
13	Correct	13744 KB	Output is correct
14	Incorrect	13744 KB	Output isn't correct
15	Correct	13744 KB	Output is correct
16	Incorrect	13744 KB	Output isn't correct
17	Correct	13744 KB	Output is correct
18	Incorrect	13744 KB	Output isn't correct
19	Correct	13744 KB	Output is correct
20	Incorrect	13744 KB	Output isn't correct
21	Correct	13744 KB	Output is correct
22	Incorrect	13744 KB	Output isn't correct
23	Correct	13744 KB	Output is correct
24	Correct	13744 KB	Output is correct
25	Incorrect	13744 KB	Output isn't correct
26	Incorrect	13744 KB	Output isn't correct
27	Incorrect	13744 KB	Output isn't correct
28	Incorrect	13744 KB	Output isn't correct
29	Incorrect	13744 KB	Output isn't correct
30	Correct	13744 KB	Output is correct
31	Correct	13744 KB	Output is correct
32	Correct	13744 KB	Output is correct
33	Incorrect	13744 KB	Output isn't correct
34	Incorrect	13744 KB	Output isn't correct
35	Incorrect	13744 KB	Output isn't correct
36	Correct	13744 KB	Output is correct
37	Incorrect	13744 KB	Output isn't correct
38	Incorrect	13744 KB	Output isn't correct
39	Incorrect	13744 KB	Output isn't correct
40	Correct	13744 KB	Output is correct
41	Incorrect	13744 KB	Output isn't correct
42	Incorrect	13744 KB	Output isn't correct
43	Incorrect	13744 KB	Output isn't correct
44	Incorrect	13744 KB	Output isn't correct
45	Incorrect	13744 KB	Output isn't correct
46	Incorrect	13744 KB	Output isn't correct
47	Correct	13744 KB	Output is correct
48	Incorrect	13744 KB	Output isn't correct
49	Incorrect	13744 KB	Output isn't correct
50	Incorrect	13744 KB	Output isn't correct
51	Incorrect	13744 KB	Output isn't correct
52	Correct	13744 KB	Output is correct
53	Incorrect	13744 KB	Output isn't correct

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	13744 KB	Output is correct
2	Incorrect	0 ms	13744 KB	Output isn't correct
3	Incorrect	0 ms	13744 KB	Output isn't correct
4	Correct	0 ms	13744 KB	Output is correct
5	Correct	0 ms	13744 KB	Output is correct
6	Correct	0 ms	13744 KB	Output is correct
7	Correct	0 ms	13744 KB	Output is correct
8	Incorrect	0 ms	13744 KB	Output isn't correct
9	Correct	0 ms	13744 KB	Output is correct
10	Incorrect	0 ms	13744 KB	Output isn't correct
11	Correct	0 ms	13744 KB	Output is correct
12	Correct	0 ms	13744 KB	Output is correct
13	Correct	0 ms	13744 KB	Output is correct
14	Incorrect	0 ms	13744 KB	Output isn't correct
15	Correct	0 ms	13744 KB	Output is correct
16	Incorrect	0 ms	13744 KB	Output isn't correct
17	Correct	0 ms	13744 KB	Output is correct
18	Incorrect	0 ms	13744 KB	Output isn't correct
19	Correct	0 ms	13744 KB	Output is correct
20	Incorrect	0 ms	13744 KB	Output isn't correct
21	Correct	0 ms	13744 KB	Output is correct
22	Incorrect	0 ms	13744 KB	Output isn't correct
23	Correct	0 ms	13744 KB	Output is correct
24	Correct	0 ms	13744 KB	Output is correct
25	Incorrect	0 ms	13744 KB	Output isn't correct
26	Incorrect	0 ms	13744 KB	Output isn't correct
27	Incorrect	0 ms	13744 KB	Output isn't correct
28	Incorrect	0 ms	13744 KB	Output isn't correct
29	Incorrect	0 ms	13744 KB	Output isn't correct
30	Correct	0 ms	13744 KB	Output is correct
31	Correct	0 ms	13744 KB	Output is correct
32	Correct	0 ms	13744 KB	Output is correct
33	Incorrect	0 ms	13744 KB	Output isn't correct
34	Incorrect	0 ms	13744 KB	Output isn't correct
35	Incorrect	0 ms	13744 KB	Output isn't correct
36	Correct	0 ms	13744 KB	Output is correct
37	Incorrect	0 ms	13744 KB	Output isn't correct
38	Incorrect	0 ms	13744 KB	Output isn't correct
39	Incorrect	0 ms	13744 KB	Output isn't correct
40	Correct	0 ms	13744 KB	Output is correct
41	Incorrect	0 ms	13744 KB	Output isn't correct
42	Incorrect	0 ms	13744 KB	Output isn't correct
43	Incorrect	0 ms	13744 KB	Output isn't correct
44	Incorrect	0 ms	13744 KB	Output isn't correct
45	Incorrect	0 ms	13744 KB	Output isn't correct
46	Incorrect	0 ms	13744 KB	Output isn't correct
47	Correct	0 ms	13744 KB	Output is correct
48	Incorrect	0 ms	13744 KB	Output isn't correct
49	Incorrect	0 ms	13744 KB	Output isn't correct
50	Incorrect	0 ms	13744 KB	Output isn't correct
51	Incorrect	0 ms	13744 KB	Output isn't correct
52	Correct	0 ms	13744 KB	Output is correct
53	Incorrect	0 ms	13744 KB	Output isn't correct
54	Incorrect	0 ms	13744 KB	Output isn't correct
55	Incorrect	6 ms	14020 KB	Output isn't correct
56	Correct	6 ms	14020 KB	Output is correct
57	Incorrect	6 ms	14020 KB	Output isn't correct
58	Incorrect	6 ms	14020 KB	Output isn't correct
59	Incorrect	3 ms	14020 KB	Output isn't correct
60	Incorrect	6 ms	14020 KB	Output isn't correct
61	Correct	3 ms	14020 KB	Output is correct
62	Incorrect	6 ms	13888 KB	Output isn't correct
63	Incorrect	0 ms	13744 KB	Output isn't correct
64	Incorrect	3 ms	14020 KB	Output isn't correct
65	Incorrect	6 ms	14020 KB	Output isn't correct
66	Incorrect	6 ms	14020 KB	Output isn't correct
67	Incorrect	3 ms	13888 KB	Output isn't correct
68	Incorrect	0 ms	13888 KB	Output isn't correct
69	Correct	0 ms	14020 KB	Output is correct

Subtask #5
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	13744 KB	Output is correct
2	Incorrect	0 ms	13744 KB	Output isn't correct
3	Incorrect	0 ms	13744 KB	Output isn't correct
4	Correct	0 ms	13744 KB	Output is correct
5	Correct	0 ms	13744 KB	Output is correct
6	Correct	0 ms	13744 KB	Output is correct
7	Correct	0 ms	13744 KB	Output is correct
8	Incorrect	0 ms	13744 KB	Output isn't correct
9	Correct	0 ms	13744 KB	Output is correct
10	Incorrect	0 ms	13744 KB	Output isn't correct
11	Correct	0 ms	13744 KB	Output is correct
12	Correct	0 ms	13744 KB	Output is correct
13	Correct	0 ms	13744 KB	Output is correct
14	Incorrect	0 ms	13744 KB	Output isn't correct
15	Correct	0 ms	13744 KB	Output is correct
16	Incorrect	0 ms	13744 KB	Output isn't correct
17	Correct	0 ms	13744 KB	Output is correct
18	Incorrect	0 ms	13744 KB	Output isn't correct
19	Correct	0 ms	13744 KB	Output is correct
20	Incorrect	0 ms	13744 KB	Output isn't correct
21	Correct	0 ms	13744 KB	Output is correct
22	Incorrect	0 ms	13744 KB	Output isn't correct
23	Correct	0 ms	13744 KB	Output is correct
24	Correct	0 ms	13744 KB	Output is correct
25	Incorrect	0 ms	13744 KB	Output isn't correct
26	Incorrect	0 ms	13744 KB	Output isn't correct
27	Incorrect	0 ms	13744 KB	Output isn't correct
28	Incorrect	0 ms	13744 KB	Output isn't correct
29	Incorrect	0 ms	13744 KB	Output isn't correct
30	Correct	0 ms	13744 KB	Output is correct
31	Correct	0 ms	13744 KB	Output is correct
32	Correct	0 ms	13744 KB	Output is correct
33	Incorrect	0 ms	13744 KB	Output isn't correct
34	Incorrect	0 ms	13744 KB	Output isn't correct
35	Incorrect	0 ms	13744 KB	Output isn't correct
36	Correct	0 ms	13744 KB	Output is correct
37	Incorrect	0 ms	13744 KB	Output isn't correct
38	Incorrect	0 ms	13744 KB	Output isn't correct
39	Incorrect	0 ms	13744 KB	Output isn't correct
40	Correct	0 ms	13744 KB	Output is correct
41	Incorrect	0 ms	13744 KB	Output isn't correct
42	Incorrect	0 ms	13744 KB	Output isn't correct
43	Incorrect	0 ms	13744 KB	Output isn't correct
44	Incorrect	0 ms	13744 KB	Output isn't correct
45	Incorrect	0 ms	13744 KB	Output isn't correct
46	Incorrect	0 ms	13744 KB	Output isn't correct
47	Correct	0 ms	13744 KB	Output is correct
48	Incorrect	0 ms	13744 KB	Output isn't correct
49	Incorrect	0 ms	13744 KB	Output isn't correct
50	Incorrect	0 ms	13744 KB	Output isn't correct
51	Incorrect	0 ms	13744 KB	Output isn't correct
52	Correct	0 ms	13744 KB	Output is correct
53	Incorrect	0 ms	13744 KB	Output isn't correct
54	Incorrect	0 ms	13744 KB	Output isn't correct
55	Incorrect	6 ms	14020 KB	Output isn't correct
56	Correct	6 ms	14020 KB	Output is correct
57	Incorrect	6 ms	14020 KB	Output isn't correct
58	Incorrect	6 ms	14020 KB	Output isn't correct
59	Incorrect	3 ms	14020 KB	Output isn't correct
60	Incorrect	6 ms	14020 KB	Output isn't correct
61	Correct	3 ms	14020 KB	Output is correct
62	Incorrect	6 ms	13888 KB	Output isn't correct
63	Incorrect	0 ms	13744 KB	Output isn't correct
64	Incorrect	3 ms	14020 KB	Output isn't correct
65	Incorrect	6 ms	14020 KB	Output isn't correct
66	Incorrect	6 ms	14020 KB	Output isn't correct
67	Incorrect	3 ms	13888 KB	Output isn't correct
68	Incorrect	0 ms	13888 KB	Output isn't correct
69	Correct	0 ms	14020 KB	Output is correct
70	Incorrect	6 ms	14020 KB	Output isn't correct
71	Incorrect	149 ms	16904 KB	Output isn't correct
72	Correct	119 ms	16904 KB	Output is correct
73	Incorrect	156 ms	16904 KB	Output isn't correct
74	Incorrect	126 ms	16904 KB	Output isn't correct
75	Incorrect	146 ms	16904 KB	Output isn't correct
76	Incorrect	143 ms	16904 KB	Output isn't correct
77	Incorrect	63 ms	15368 KB	Output isn't correct
78	Incorrect	159 ms	16904 KB	Output isn't correct
79	Incorrect	149 ms	16904 KB	Output isn't correct
80	Correct	139 ms	16904 KB	Output is correct
81	Incorrect	29 ms	14600 KB	Output isn't correct
82	Incorrect	109 ms	16904 KB	Output isn't correct
83	Incorrect	149 ms	16904 KB	Output isn't correct
84	Incorrect	146 ms	16904 KB	Output isn't correct
85	Incorrect	136 ms	16904 KB	Output isn't correct
86	Incorrect	146 ms	16904 KB	Output isn't correct
87	Correct	143 ms	16904 KB	Output is correct
88	Incorrect	19 ms	14216 KB	Output isn't correct
89	Incorrect	79 ms	15368 KB	Output isn't correct
90	Incorrect	63 ms	15368 KB	Output isn't correct
91	Incorrect	6 ms	14020 KB	Output isn't correct
92	Incorrect	56 ms	15368 KB	Output isn't correct

Submission #20497

Compilation message

Subtask #1 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
0 / 11.0

Subtask #2
0 / 12.0

Subtask #3
0 / 23.0

Subtask #4
0 / 26.0

Subtask #5
0 / 28.0