Submission #20673

#	Time	Username	Problem	Language	Result	Execution time	Memory
20673		errorist (#35)	Can polan into space? (OJUZ11_space)	C++14	0 / 100	1000 ms	29060 KiB

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 (stderr)

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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 26
• Subtask 5: 0 / 28