Submission #20341

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
20341	2017-02-07T06:08:22 Z		Can polan into space? (OJUZ11_space)	C++11	0 / 100	1098 ms	54564 KB

space

#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int N;
const int MAX_N = 200010;

ll a[MAX_N][3],sum[MAX_N][3];

ll dp[MAX_N],path[MAX_N],pick[MAX_N];

void f(int x,vector<int>& s){
	if(x==0)return;
	f(path[x],s);
	s.push_back(x);
}

int main(){
	
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		for(int j=0;j<3;j++){
			scanf("%lld",&a[i][j]);
			sum[i][j]+=sum[i-1][j]+a[i][j];
		}
	}

	for(int i=1;i<=N;i++){
		dp[i]=sum[i-1][1]+a[i][0];
		ll pmax=a[i-1][2]-a[i-1][1],v;
		for(int j=i-2;j>0;j--){
			if(pmax<a[j+1][2]-a[j+1][1]){
				pmax=a[j+1][2]-a[j+1][1];
				v=j+1;
			}
			if(dp[i]<dp[j]+pmax+sum[i-1][1]-sum[j][1]+a[i][0]){
				dp[i]=dp[j]+pmax+sum[i-1][1]-sum[j][1]+a[i][0];
				pick[i]=v;
				path[i]=j;
			}
		}
	}

	ll ans=0,v;
	for(int i=1;i<=N;i++){
		if(ans<dp[i]+sum[N][1]-sum[i][1]){
			ans=dp[i]+sum[N][1]-sum[i][1];
			v=i;
		}
	}

	printf("%lld\n",ans);

	vector<int> st;
	f(v,st);

	assert(!st.empty());

	for(int i:st){
		printf("%d ",i);
	}

	for(int i=st.front()-1;i>=1;i--)printf("%d ",i);
	for(int i=st.back()+1;i<=N;i++)printf("%d ",i);
	
	for(int i=1;i<st.size();i++){
		for(int j=st[i-1]+1;j<pick[st[i]];j++)printf("%d ",j);
		for(int j=st[i]-1;j>=pick[st[i]];j--)printf("%d ",j);
	}
	puts("");

	return 0;
}

Compilation message

space.cpp: In function 'int main()':
space.cpp:70:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<st.size();i++){
               ^
space.cpp:24:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
space.cpp:27:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld",&a[i][j]);
                          ^
space.cpp:59:3: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  f(v,st);
   ^
space.cpp:42:14: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
     pick[i]=v;
              ^

Subtask #1
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	268 KB	Output is correct
2	Correct	1 ms	444 KB	Output is correct
3	Correct	1 ms	444 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Incorrect	709 ms	51632 KB	Output isn't correct
7	Correct	9 ms	53660 KB	Output is correct
8	Correct	1 ms	53660 KB	Output is correct
9	Correct	1 ms	53660 KB	Output is correct
10	Correct	1 ms	53660 KB	Output is correct
11	Incorrect	1 ms	53660 KB	Extra information in the output file
12	Incorrect	656 ms	53660 KB	Output isn't correct
13	Incorrect	10 ms	53668 KB	Extra information in the output file
14	Correct	1 ms	53668 KB	Output is correct
15	Incorrect	728 ms	53668 KB	Extra information in the output file
16	Correct	9 ms	53668 KB	Output is correct
17	Correct	1 ms	53668 KB	Output is correct
18	Incorrect	652 ms	53668 KB	Output isn't correct
19	Incorrect	666 ms	53668 KB	Output isn't correct
20	Incorrect	677 ms	53668 KB	Output isn't correct
21	Incorrect	692 ms	53668 KB	Output isn't correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	268 KB	Output is correct
2	Correct	1 ms	444 KB	Output is correct
3	Correct	1 ms	444 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Incorrect	709 ms	51632 KB	Output isn't correct
7	Correct	9 ms	53660 KB	Output is correct
8	Correct	1 ms	53660 KB	Output is correct
9	Correct	1 ms	53660 KB	Output is correct
10	Correct	1 ms	53660 KB	Output is correct
11	Incorrect	1 ms	53660 KB	Extra information in the output file
12	Incorrect	656 ms	53660 KB	Output isn't correct
13	Incorrect	10 ms	53668 KB	Extra information in the output file
14	Correct	1 ms	53668 KB	Output is correct
15	Incorrect	728 ms	53668 KB	Extra information in the output file
16	Correct	9 ms	53668 KB	Output is correct
17	Correct	1 ms	53668 KB	Output is correct
18	Incorrect	652 ms	53668 KB	Output isn't correct
19	Incorrect	666 ms	53668 KB	Output isn't correct
20	Incorrect	677 ms	53668 KB	Output isn't correct
21	Incorrect	692 ms	53668 KB	Output isn't correct
22	Correct	9 ms	53668 KB	Output is correct
23	Incorrect	650 ms	53668 KB	Output isn't correct
24	Correct	9 ms	53668 KB	Output is correct
25	Incorrect	1 ms	53668 KB	Extra information in the output file
26	Incorrect	1 ms	53668 KB	Output isn't correct
27	Incorrect	1 ms	53668 KB	Output isn't correct
28	Correct	1 ms	53668 KB	Output is correct
29	Incorrect	1 ms	53668 KB	Output isn't correct
30	Incorrect	1 ms	53668 KB	Output isn't correct
31	Correct	1 ms	53668 KB	Output is correct
32	Incorrect	706 ms	53668 KB	Output isn't correct
33	Incorrect	10 ms	53668 KB	Output isn't correct
34	Incorrect	1 ms	53668 KB	Output isn't correct
35	Incorrect	1 ms	53668 KB	Output isn't correct
36	Incorrect	654 ms	53668 KB	Output isn't correct
37	Incorrect	9 ms	53668 KB	Output isn't correct

Subtask #3
0 / 23.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	268 KB	Output is correct
2	Correct	1 ms	444 KB	Output is correct
3	Correct	1 ms	444 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Incorrect	709 ms	51632 KB	Output isn't correct
7	Correct	9 ms	53660 KB	Output is correct
8	Correct	1 ms	53660 KB	Output is correct
9	Correct	1 ms	53660 KB	Output is correct
10	Correct	1 ms	53660 KB	Output is correct
11	Incorrect	1 ms	53660 KB	Extra information in the output file
12	Incorrect	656 ms	53660 KB	Output isn't correct
13	Incorrect	10 ms	53668 KB	Extra information in the output file
14	Correct	1 ms	53668 KB	Output is correct
15	Incorrect	728 ms	53668 KB	Extra information in the output file
16	Correct	9 ms	53668 KB	Output is correct
17	Correct	1 ms	53668 KB	Output is correct
18	Incorrect	652 ms	53668 KB	Output isn't correct
19	Incorrect	666 ms	53668 KB	Output isn't correct
20	Incorrect	677 ms	53668 KB	Output isn't correct
21	Incorrect	692 ms	53668 KB	Output isn't correct
22	Correct	9 ms	53668 KB	Output is correct
23	Incorrect	650 ms	53668 KB	Output isn't correct
24	Correct	9 ms	53668 KB	Output is correct
25	Incorrect	1 ms	53668 KB	Extra information in the output file
26	Incorrect	1 ms	53668 KB	Output isn't correct
27	Incorrect	1 ms	53668 KB	Output isn't correct
28	Correct	1 ms	53668 KB	Output is correct
29	Incorrect	1 ms	53668 KB	Output isn't correct
30	Incorrect	1 ms	53668 KB	Output isn't correct
31	Correct	1 ms	53668 KB	Output is correct
32	Incorrect	706 ms	53668 KB	Output isn't correct
33	Incorrect	10 ms	53668 KB	Output isn't correct
34	Incorrect	1 ms	53668 KB	Output isn't correct
35	Incorrect	1 ms	53668 KB	Output isn't correct
36	Incorrect	654 ms	53668 KB	Output isn't correct
37	Incorrect	9 ms	53668 KB	Output isn't correct
38	Incorrect	1 ms	53668 KB	Output isn't correct
39	Incorrect	2 ms	53668 KB	Output isn't correct
40	Correct	1 ms	53668 KB	Output is correct
41	Incorrect	655 ms	53668 KB	Output isn't correct
42	Incorrect	11 ms	53796 KB	Output isn't correct
43	Incorrect	2 ms	53796 KB	Output isn't correct
44	Correct	2 ms	53796 KB	Output is correct
45	Incorrect	2 ms	53796 KB	Output isn't correct
46	Incorrect	689 ms	53796 KB	Output isn't correct
47	Correct	9 ms	53796 KB	Output is correct
48	Incorrect	1 ms	53796 KB	Output isn't correct
49	Incorrect	712 ms	53796 KB	Output isn't correct
50	Execution timed out	1098 ms	53796 KB	Time limit exceeded
51	Incorrect	10 ms	53796 KB	Output isn't correct
52	Incorrect	656 ms	53796 KB	Output isn't correct
53	Incorrect	9 ms	53796 KB	Output isn't correct

Subtask #4
0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	268 KB	Output is correct
2	Correct	1 ms	444 KB	Output is correct
3	Correct	1 ms	444 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Incorrect	709 ms	51632 KB	Output isn't correct
7	Correct	9 ms	53660 KB	Output is correct
8	Correct	1 ms	53660 KB	Output is correct
9	Correct	1 ms	53660 KB	Output is correct
10	Correct	1 ms	53660 KB	Output is correct
11	Incorrect	1 ms	53660 KB	Extra information in the output file
12	Incorrect	656 ms	53660 KB	Output isn't correct
13	Incorrect	10 ms	53668 KB	Extra information in the output file
14	Correct	1 ms	53668 KB	Output is correct
15	Incorrect	728 ms	53668 KB	Extra information in the output file
16	Correct	9 ms	53668 KB	Output is correct
17	Correct	1 ms	53668 KB	Output is correct
18	Incorrect	652 ms	53668 KB	Output isn't correct
19	Incorrect	666 ms	53668 KB	Output isn't correct
20	Incorrect	677 ms	53668 KB	Output isn't correct
21	Incorrect	692 ms	53668 KB	Output isn't correct
22	Correct	9 ms	53668 KB	Output is correct
23	Incorrect	650 ms	53668 KB	Output isn't correct
24	Correct	9 ms	53668 KB	Output is correct
25	Incorrect	1 ms	53668 KB	Extra information in the output file
26	Incorrect	1 ms	53668 KB	Output isn't correct
27	Incorrect	1 ms	53668 KB	Output isn't correct
28	Correct	1 ms	53668 KB	Output is correct
29	Incorrect	1 ms	53668 KB	Output isn't correct
30	Incorrect	1 ms	53668 KB	Output isn't correct
31	Correct	1 ms	53668 KB	Output is correct
32	Incorrect	706 ms	53668 KB	Output isn't correct
33	Incorrect	10 ms	53668 KB	Output isn't correct
34	Incorrect	1 ms	53668 KB	Output isn't correct
35	Incorrect	1 ms	53668 KB	Output isn't correct
36	Incorrect	654 ms	53668 KB	Output isn't correct
37	Incorrect	9 ms	53668 KB	Output isn't correct
38	Incorrect	1 ms	53668 KB	Output isn't correct
39	Incorrect	2 ms	53668 KB	Output isn't correct
40	Correct	1 ms	53668 KB	Output is correct
41	Incorrect	655 ms	53668 KB	Output isn't correct
42	Incorrect	11 ms	53796 KB	Output isn't correct
43	Incorrect	2 ms	53796 KB	Output isn't correct
44	Correct	2 ms	53796 KB	Output is correct
45	Incorrect	2 ms	53796 KB	Output isn't correct
46	Incorrect	689 ms	53796 KB	Output isn't correct
47	Correct	9 ms	53796 KB	Output is correct
48	Incorrect	1 ms	53796 KB	Output isn't correct
49	Incorrect	712 ms	53796 KB	Output isn't correct
50	Execution timed out	1098 ms	53796 KB	Time limit exceeded
51	Incorrect	10 ms	53796 KB	Output isn't correct
52	Incorrect	656 ms	53796 KB	Output isn't correct
53	Incorrect	9 ms	53796 KB	Output isn't correct
54	Incorrect	656 ms	53796 KB	Output isn't correct
55	Incorrect	437 ms	53796 KB	Output isn't correct
56	Correct	138 ms	53796 KB	Output is correct
57	Incorrect	273 ms	53796 KB	Output isn't correct
58	Incorrect	405 ms	53796 KB	Output isn't correct
59	Incorrect	975 ms	53796 KB	Output isn't correct
60	Incorrect	770 ms	54564 KB	Output isn't correct
61	Correct	158 ms	54564 KB	Output is correct
62	Execution timed out	1092 ms	54564 KB	Time limit exceeded
63	Incorrect	854 ms	54564 KB	Output isn't correct
64	Incorrect	338 ms	54564 KB	Output isn't correct
65	Correct	133 ms	54564 KB	Output is correct
66	Incorrect	402 ms	54564 KB	Output isn't correct
67	Incorrect	813 ms	54564 KB	Output isn't correct
68	Incorrect	78 ms	54564 KB	Output isn't correct
69	Execution timed out	1089 ms	54564 KB	Time limit exceeded

Subtask #5
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	268 KB	Output is correct
2	Correct	1 ms	444 KB	Output is correct
3	Correct	1 ms	444 KB	Output is correct
4	Correct	1 ms	444 KB	Output is correct
5	Correct	1 ms	444 KB	Output is correct
6	Incorrect	709 ms	51632 KB	Output isn't correct
7	Correct	9 ms	53660 KB	Output is correct
8	Correct	1 ms	53660 KB	Output is correct
9	Correct	1 ms	53660 KB	Output is correct
10	Correct	1 ms	53660 KB	Output is correct
11	Incorrect	1 ms	53660 KB	Extra information in the output file
12	Incorrect	656 ms	53660 KB	Output isn't correct
13	Incorrect	10 ms	53668 KB	Extra information in the output file
14	Correct	1 ms	53668 KB	Output is correct
15	Incorrect	728 ms	53668 KB	Extra information in the output file
16	Correct	9 ms	53668 KB	Output is correct
17	Correct	1 ms	53668 KB	Output is correct
18	Incorrect	652 ms	53668 KB	Output isn't correct
19	Incorrect	666 ms	53668 KB	Output isn't correct
20	Incorrect	677 ms	53668 KB	Output isn't correct
21	Incorrect	692 ms	53668 KB	Output isn't correct
22	Correct	9 ms	53668 KB	Output is correct
23	Incorrect	650 ms	53668 KB	Output isn't correct
24	Correct	9 ms	53668 KB	Output is correct
25	Incorrect	1 ms	53668 KB	Extra information in the output file
26	Incorrect	1 ms	53668 KB	Output isn't correct
27	Incorrect	1 ms	53668 KB	Output isn't correct
28	Correct	1 ms	53668 KB	Output is correct
29	Incorrect	1 ms	53668 KB	Output isn't correct
30	Incorrect	1 ms	53668 KB	Output isn't correct
31	Correct	1 ms	53668 KB	Output is correct
32	Incorrect	706 ms	53668 KB	Output isn't correct
33	Incorrect	10 ms	53668 KB	Output isn't correct
34	Incorrect	1 ms	53668 KB	Output isn't correct
35	Incorrect	1 ms	53668 KB	Output isn't correct
36	Incorrect	654 ms	53668 KB	Output isn't correct
37	Incorrect	9 ms	53668 KB	Output isn't correct
38	Incorrect	1 ms	53668 KB	Output isn't correct
39	Incorrect	2 ms	53668 KB	Output isn't correct
40	Correct	1 ms	53668 KB	Output is correct
41	Incorrect	655 ms	53668 KB	Output isn't correct
42	Incorrect	11 ms	53796 KB	Output isn't correct
43	Incorrect	2 ms	53796 KB	Output isn't correct
44	Correct	2 ms	53796 KB	Output is correct
45	Incorrect	2 ms	53796 KB	Output isn't correct
46	Incorrect	689 ms	53796 KB	Output isn't correct
47	Correct	9 ms	53796 KB	Output is correct
48	Incorrect	1 ms	53796 KB	Output isn't correct
49	Incorrect	712 ms	53796 KB	Output isn't correct
50	Execution timed out	1098 ms	53796 KB	Time limit exceeded
51	Incorrect	10 ms	53796 KB	Output isn't correct
52	Incorrect	656 ms	53796 KB	Output isn't correct
53	Incorrect	9 ms	53796 KB	Output isn't correct
54	Incorrect	656 ms	53796 KB	Output isn't correct
55	Incorrect	437 ms	53796 KB	Output isn't correct
56	Correct	138 ms	53796 KB	Output is correct
57	Incorrect	273 ms	53796 KB	Output isn't correct
58	Incorrect	405 ms	53796 KB	Output isn't correct
59	Incorrect	975 ms	53796 KB	Output isn't correct
60	Incorrect	770 ms	54564 KB	Output isn't correct
61	Correct	158 ms	54564 KB	Output is correct
62	Execution timed out	1092 ms	54564 KB	Time limit exceeded
63	Incorrect	854 ms	54564 KB	Output isn't correct
64	Incorrect	338 ms	54564 KB	Output isn't correct
65	Correct	133 ms	54564 KB	Output is correct
66	Incorrect	402 ms	54564 KB	Output isn't correct
67	Incorrect	813 ms	54564 KB	Output isn't correct
68	Incorrect	78 ms	54564 KB	Output isn't correct
69	Execution timed out	1089 ms	54564 KB	Time limit exceeded
70	Incorrect	543 ms	54564 KB	Output isn't correct
71	Execution timed out	1079 ms	54564 KB	Time limit exceeded
72	Execution timed out	1085 ms	54564 KB	Time limit exceeded
73	Execution timed out	1086 ms	54564 KB	Time limit exceeded
74	Execution timed out	1088 ms	54564 KB	Time limit exceeded
75	Execution timed out	1084 ms	54564 KB	Time limit exceeded
76	Execution timed out	1085 ms	54564 KB	Time limit exceeded
77	Execution timed out	1084 ms	54564 KB	Time limit exceeded
78	Execution timed out	1081 ms	54564 KB	Time limit exceeded
79	Execution timed out	1088 ms	54564 KB	Time limit exceeded
80	Execution timed out	1083 ms	54564 KB	Time limit exceeded
81	Execution timed out	1087 ms	54564 KB	Time limit exceeded
82	Execution timed out	1081 ms	54564 KB	Time limit exceeded
83	Execution timed out	1082 ms	54564 KB	Time limit exceeded
84	Execution timed out	1084 ms	54564 KB	Time limit exceeded
85	Execution timed out	1086 ms	54564 KB	Time limit exceeded
86	Execution timed out	1088 ms	54564 KB	Time limit exceeded
87	Execution timed out	1084 ms	54564 KB	Time limit exceeded
88	Execution timed out	1079 ms	54564 KB	Time limit exceeded
89	Execution timed out	1083 ms	54564 KB	Time limit exceeded
90	Execution timed out	1084 ms	54564 KB	Time limit exceeded
91	Correct	123 ms	54564 KB	Output is correct
92	Execution timed out	1087 ms	54564 KB	Time limit exceeded

Submission #20341

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