Submission #20480

#	Time	Username	Problem	Language	Result	Execution time	Memory
20480		볼빨간민돌이 (#35)	Can polan into space? (OJUZ11_space)	C++11	100 / 100	133 ms	14272 KiB

space

#include <cstdio>

int n, a[200001], b[200001], c[200001];

long long dp_oo[200001]; int opt_oo[200001];
long long dp_ov[200001]; int opt_ov[200001];

void trace(int type, int i){
	if(i==1){
		printf("1 ");
		return;
	}

    if(type==1){
		if(opt_oo[i]==1){
			printf("%d ", i);
			trace(2, i-1);
		}
		else{
			trace(1, i-1);
			printf("%d ", i);
		}
    }
    else{
		if(opt_ov[i]==1){
			printf("%d ", i);
			trace(2, i-1);
		}
		else{
			trace(1, i-1);
			printf("%d ", i);
		}
    }
}

int main(){
	scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%d %d %d", &a[i], &b[i], &c[i]);

    dp_oo[1]=a[1];
    dp_ov[1]=b[1];
    for(int i=2; i<=n; i++){
        dp_oo[i]=dp_ov[i-1]+a[i];
        opt_oo[i]=1;
        if(dp_oo[i] < dp_oo[i-1]+b[i]){
			dp_oo[i]=dp_oo[i-1]+b[i];
			opt_oo[i]=2;
        }

        dp_ov[i]=dp_ov[i-1]+b[i];
        opt_ov[i]=1;
        if(dp_ov[i] < dp_oo[i-1]+c[i]){
			dp_ov[i]=dp_oo[i-1]+c[i];
			opt_ov[i]=2;
        }
    }

    printf("%lld\n", dp_oo[n]);
    trace(1, n);
	return 0;
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:37:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
space.cpp:39:47: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a[i], &b[i], &c[i]);
                                               ^

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