답안 #20673 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20673	2017-02-13T13:07:59 Z	errorist(#79, andy627)	Can polan into space? (OJUZ11_space)	C++14	0 / 100	1000 ms	29060 KB

space

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

int n,cnt;
int mp[222222][3],ord[222222];
int ph[3][3][222222];
bool used[222222];
long long dp[3][3][222222];
queue<int> q;

void bfs(int p){
    while(!q.empty()) q.pop();
    q.push(p);

    int done=0;
    if(used[p+1]) done++;
    if(used[p-1]) done++;
    if(done!=ord[p]) return;

    printf("%d ",p);
    used[p]=1; cnt++;
    while(!q.empty()){
        int np=q.front();
        if(np+1<=n && !used[np+1]){
            done=0;
            if(used[np+2]) done++;
            if(used[np]) done++;
            if(done!=ord[np+1]) return;

            q.push(np+1);
            printf("%d ",np+1);
            used[np+1]=1;
        }
        if(np-1>=1 && !used[np-1]){
            done=0;
            if(used[np]) done++;
            if(used[np-2]) done++;
            if(done!=ord[np]) return;

            q.push(np-1);
            printf("%d ",np-1);
            used[np-1]=1;
        }
        q.pop();
    }
    return;
}


int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++) scanf("%d",&mp[i][j]);
    }
    if(n==1){
        printf("%d\n1",mp[1][0]);
        return 0;
    }


    for(int i=0;i<2;i++){
        for(int j=0;j<3;j++) dp[i][j][2]=mp[1][i]+mp[2][j];
    }

    for(int i=3;i<=n;i++){
        dp[0][1][i]=max(dp[1][0][i-1],dp[2][0][i-1])+mp[i][1];
        dp[0][2][i]=max(dp[1][0][i-1],dp[2][0][i-1])+mp[i][2];
        if(dp[0][1][i]==dp[1][0][i-1]+mp[i][1]) ph[0][1][i]=1;
        else ph[0][1][i]=2;

        dp[1][0][i]=max(dp[1][1][i-1],dp[2][1][i-1])+mp[i][0];
        if(dp[1][0][i]==dp[1][1][i-1]+mp[i][0]) ph[1][0][i]=1;
        else ph[1][0][i]=2;

        dp[1][1][i]=max(dp[0][1][i-1],max(dp[1][1][i-1],dp[2][1][i-1]))+mp[i][1];
        dp[1][2][i]=max(dp[0][1][i-1],max(dp[1][1][i-1],dp[2][1][i-1]))+mp[i][2];
        if(dp[1][1][i]==dp[1][1][i-1]+mp[i][1]) ph[1][1][i]=ph[1][2][i]=1;
        else if(dp[1][1][i]==dp[2][1][i-1]+mp[i][1]) ph[1][1][i]=ph[1][2][i]=2;

        dp[2][0][i]=max(dp[0][2][i-1],dp[1][2][i-1])+mp[i][0];
        dp[2][1][i]=max(dp[0][2][i-1],dp[1][2][i-1])+mp[i][1];
        if(dp[2][0][i]==dp[1][2][i-1]+mp[i][0]) ph[2][0][i]=ph[2][1][i]=1;
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<3;k++) printf("%d ",dp[j][k][i]);
        }
        printf("\n");
    }
    printf("\n");

    int pos1=0,pos2=0;
    if(max(max(dp[1][0][n],dp[2][0][n]),dp[0][1][n])==dp[0][1][n]) pos2=1;
    else{
        if(max(dp[1][0][n],dp[2][0][n])==dp[1][0][n]) pos1=1;
        else pos1=2;
    }

    ord[n-1]=pos1; ord[n]=pos2;
    for(int i=n;i>2;i--){
        ord[i-2]=ph[pos1][pos2][i];
        pos2=pos1;
        pos1=ph[pos1][pos2][i];
    }

    printf("%lld\n",max(max(dp[1][0][n],dp[2][0][n]),dp[0][1][n]));
    while(cnt!=n){
        for(int i=1;i<=n;i++){
            if(used[i]) continue;
            bfs(i);
        }
    }

    return 0;
}

Compilation message

space.cpp: In function 'int main()':
space.cpp:89:58: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
             for(int k=0;k<3;k++) printf("%d ",dp[j][k][i]);
                                                          ^
space.cpp:53:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
space.cpp:55:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int j=0;j<3;j++) scanf("%d",&mp[i][j]);
                                                   ^

Subtask #1
0 / 11.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 26.0

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

Subtask #5
0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	29060 KB	Output is correct
2	Execution timed out	1000 ms	29060 KB	Execution timed out
3	Execution timed out	1000 ms	29060 KB	Execution timed out
4	Execution timed out	1000 ms	29060 KB	Execution timed out
5	Execution timed out	1000 ms	29060 KB	Execution timed out
6	Execution timed out	1000 ms	29060 KB	Execution timed out
7	Execution timed out	1000 ms	29060 KB	Execution timed out
8	Execution timed out	1000 ms	29060 KB	Execution timed out
9	Execution timed out	1000 ms	29060 KB	Execution timed out
10	Execution timed out	1000 ms	29060 KB	Execution timed out
11	Execution timed out	1000 ms	29060 KB	Execution timed out
12	Execution timed out	1000 ms	29060 KB	Execution timed out
13	Execution timed out	1000 ms	29060 KB	Execution timed out
14	Execution timed out	1000 ms	29060 KB	Execution timed out
15	Execution timed out	1000 ms	29060 KB	Execution timed out
16	Execution timed out	1000 ms	29060 KB	Execution timed out
17	Execution timed out	1000 ms	29060 KB	Execution timed out
18	Execution timed out	1000 ms	29060 KB	Execution timed out
19	Execution timed out	1000 ms	29060 KB	Execution timed out
20	Execution timed out	1000 ms	29060 KB	Execution timed out
21	Execution timed out	1000 ms	29060 KB	Execution timed out
22	Execution timed out	1000 ms	29060 KB	Execution timed out
23	Execution timed out	1000 ms	29060 KB	Execution timed out
24	Execution timed out	1000 ms	29060 KB	Execution timed out
25	Execution timed out	1000 ms	29060 KB	Execution timed out
26	Execution timed out	1000 ms	29060 KB	Execution timed out
27	Execution timed out	1000 ms	29060 KB	Execution timed out
28	Execution timed out	1000 ms	29060 KB	Execution timed out
29	Execution timed out	1000 ms	29060 KB	Execution timed out
30	Execution timed out	1000 ms	29060 KB	Execution timed out
31	Execution timed out	1000 ms	29060 KB	Execution timed out
32	Execution timed out	1000 ms	29060 KB	Execution timed out
33	Execution timed out	1000 ms	29060 KB	Execution timed out
34	Execution timed out	1000 ms	29060 KB	Execution timed out
35	Execution timed out	1000 ms	29060 KB	Execution timed out
36	Execution timed out	1000 ms	29060 KB	Execution timed out
37	Execution timed out	1000 ms	29060 KB	Execution timed out
38	Execution timed out	1000 ms	29060 KB	Execution timed out
39	Execution timed out	1000 ms	29060 KB	Execution timed out
40	Execution timed out	1000 ms	29060 KB	Execution timed out
41	Execution timed out	1000 ms	29060 KB	Execution timed out
42	Execution timed out	1000 ms	29060 KB	Execution timed out
43	Execution timed out	1000 ms	29060 KB	Execution timed out
44	Execution timed out	1000 ms	29060 KB	Execution timed out
45	Execution timed out	1000 ms	29060 KB	Execution timed out
46	Execution timed out	1000 ms	29060 KB	Execution timed out
47	Execution timed out	1000 ms	29060 KB	Execution timed out
48	Execution timed out	1000 ms	29060 KB	Execution timed out
49	Execution timed out	1000 ms	29060 KB	Execution timed out
50	Execution timed out	1000 ms	29060 KB	Execution timed out
51	Execution timed out	1000 ms	29060 KB	Execution timed out
52	Execution timed out	1000 ms	29060 KB	Execution timed out
53	Execution timed out	1000 ms	29060 KB	Execution timed out
54	Execution timed out	1000 ms	29060 KB	Execution timed out
55	Execution timed out	1000 ms	29060 KB	Execution timed out
56	Execution timed out	1000 ms	29060 KB	Execution timed out
57	Execution timed out	1000 ms	29060 KB	Execution timed out
58	Execution timed out	1000 ms	29060 KB	Execution timed out
59	Execution timed out	1000 ms	29060 KB	Execution timed out
60	Execution timed out	1000 ms	29060 KB	Execution timed out
61	Execution timed out	1000 ms	29060 KB	Execution timed out
62	Execution timed out	1000 ms	29060 KB	Execution timed out
63	Execution timed out	1000 ms	29060 KB	Execution timed out
64	Execution timed out	1000 ms	29060 KB	Execution timed out
65	Execution timed out	1000 ms	29060 KB	Execution timed out
66	Execution timed out	1000 ms	29060 KB	Execution timed out
67	Execution timed out	1000 ms	29060 KB	Execution timed out
68	Execution timed out	1000 ms	29060 KB	Execution timed out
69	Execution timed out	1000 ms	29060 KB	Execution timed out
70	Execution timed out	1000 ms	29060 KB	Execution timed out
71	Execution timed out	1000 ms	29060 KB	Execution timed out
72	Execution timed out	1000 ms	29060 KB	Execution timed out
73	Execution timed out	1000 ms	29060 KB	Execution timed out
74	Execution timed out	1000 ms	29060 KB	Execution timed out
75	Execution timed out	1000 ms	29060 KB	Execution timed out
76	Execution timed out	1000 ms	29060 KB	Execution timed out
77	Execution timed out	1000 ms	29060 KB	Execution timed out
78	Execution timed out	1000 ms	29060 KB	Execution timed out
79	Execution timed out	1000 ms	29060 KB	Execution timed out
80	Execution timed out	1000 ms	29060 KB	Execution timed out
81	Execution timed out	1000 ms	29060 KB	Execution timed out
82	Execution timed out	1000 ms	29060 KB	Execution timed out
83	Execution timed out	1000 ms	29060 KB	Execution timed out
84	Execution timed out	1000 ms	29060 KB	Execution timed out
85	Execution timed out	1000 ms	29060 KB	Execution timed out
86	Execution timed out	1000 ms	29060 KB	Execution timed out
87	Execution timed out	1000 ms	29060 KB	Execution timed out
88	Execution timed out	1000 ms	29060 KB	Execution timed out
89	Execution timed out	1000 ms	29060 KB	Execution timed out
90	Execution timed out	1000 ms	29060 KB	Execution timed out
91	Execution timed out	1000 ms	29060 KB	Execution timed out
92	Execution timed out	1000 ms	29060 KB	Execution timed out

답안 #20673

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