Submission #20430

#	Time	Username	Problem	Language	Result	Execution time	Memory
20430		I_forgot_password (#35)	Can polan into space? (OJUZ11_space)	C++98	100 / 100	146 ms	23176 KiB

space

#include<bits/stdc++.h>
#define infll 1000000000000000000LL
using namespace std;

long long dp[200005][3][2];
long long cost[200005][3];
int prv[200005][3][2];
int ans[200005];
vector<int> gak[3];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<=n;i++){
        for(int j=0;j<3;j++){
            for(int k=0;k<2;k++){
                dp[i][j][k] = -infll;
            }
        }
    }
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&cost[i][0],&cost[i][1],&cost[i][2]);
    }
    dp[0][2][1] = 0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            /**dp[i][j][k] : j�� ����, k�� i+1��°�� i��°���� ���� �Ǿ���ϴ°�??*/
            dp[i][0][0] = max(dp[i][0][0], dp[i-1][j][1] + cost[i][0]);
            if(dp[i][0][0] == dp[i-1][j][1] + cost[i][0]) prv[i][0][0] = j;
            dp[i][1][0] = max(dp[i][1][0], dp[i-1][j][0] + cost[i][1]);
            if(dp[i][1][0] == dp[i-1][j][0] + cost[i][1]) prv[i][1][0] = j;
            dp[i][1][1] = max(dp[i][1][1], dp[i-1][j][1] + cost[i][1]);
            if(dp[i][1][1] == dp[i-1][j][1] + cost[i][1]) prv[i][1][1] = j;
            dp[i][2][1] = max(dp[i][2][1], dp[i-1][j][0] + cost[i][2]);
            if(dp[i][2][1] == dp[i-1][j][0] + cost[i][2]) prv[i][2][1] = j;
        }
        //printf("%lld %lld %lld %lld\n",dp[i][0][0],dp[i][1][0],dp[i][1][1],dp[i][2][1]);
    }
    printf("%lld\n",max(dp[n][0][0],dp[n][1][0]));
    pair<int,int> now_status;
    if(dp[n][0][0]<dp[n][1][0]) now_status = make_pair(1,0);
    else now_status = make_pair(0,0);
    for(int i=n;i>=1;i--){
        ans[i] = now_status.first;
        gak[ans[i]].push_back(i);
        now_status = make_pair(prv[i][now_status.first][now_status.second],1 + now_status.second - now_status.first);
    }
    ans[0] = 2; ans[n+1]=2;
    for(int i=0;i<gak[0].size();i++){
        printf("%d ",gak[0][i]);
        int target = gak[0][i]-1;
        while(ans[target]==1){
            printf("%d ",target);
            target--;
        }
        target = gak[0][i]+1;
        while(ans[target]==1){
            printf("%d ",target);
            target++;
        }
    }
    for(int i=0;i<gak[2].size();i++) printf("%d ",gak[2][i]);
    printf("\n");
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:21:59: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d%d%d",&cost[i][0],&cost[i][1],&cost[i][2]);
                                                           ^
space.cpp:21:59: warning: format '%d' expects argument of type 'int*', but argument 3 has type 'long long int*' [-Wformat=]
space.cpp:21:59: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'long long int*' [-Wformat=]
space.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gak[0].size();i++){
                  ^
space.cpp:61:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<gak[2].size();i++) printf("%d ",gak[2][i]);
                  ^
space.cpp:12:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
space.cpp:21:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&cost[i][0],&cost[i][1],&cost[i][2]);
                                                            ^

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 26 / 26
• Subtask 5: 28 / 28