Submission #20574

#	Time	Username	Problem	Language	Result	Execution time	Memory
20574		G (#35)	Can polan into space? (OJUZ11_space)	C++11	100 / 100	146 ms	10496 KiB

space

#include<stdio.h>
int n;
int a[200100][3];
long long int dp[200100][2];
int back[200100][2];
int gr[200100];
int ans[400100];
int anss, anse;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
	}
	dp[0][0] = a[0][0];
	dp[0][1] = a[0][1];
	for (int i = 1; i < n; i++) {
		dp[i][0] = dp[i - 1][0] + a[i][1];
		back[i][0] = 0;
		if (dp[i][0] < dp[i - 1][1] + a[i][0]) {
			dp[i][0] = dp[i - 1][1] + a[i][0];
			back[i][0] = 1;
		}
		dp[i][1] = dp[i - 1][0] + a[i][2];
		back[i][1] = 0;
		if (dp[i][1] < dp[i - 1][1] + a[i][1]) {
			dp[i][1] = dp[i - 1][1] + a[i][1];
			back[i][1] = 1;
		}
	}
	printf("%lld\n", dp[n - 1][0]);
	int p = 0;
	for (int i = n - 1; i > 0; i--) {
		p = back[i][p];
		gr[i] = p;
	}
	anss = n;
	anse = n;
	ans[n] = 0;
	for (int i = 1; i < n; i++) {
		if (gr[i] == 1) {
			anss--;
			ans[anss] = i;
		}
		else {
			anse++;
			ans[anse] = i;
		}
	}
	for (int i = anss; i <= anse; i++) {
		if(i!=anse)printf("%d ", ans[i] + 1);
		else printf("%d\n", ans[i] + 1);
	}
	return 0;
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:10:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
space.cpp:12:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &a[i][0], &a[i][1], &a[i][2]);
                                                ^

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