Submission #20571

#	Time	Username	Problem	Language	Result	Execution time	Memory
20571		CodingAmolang (#35)	Can polan into space? (OJUZ11_space)	C++11	100 / 100	173 ms	22988 KiB

space

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using std::vector;
vector<int> G[200100];
int in[200100];
long long dy[200100][2];
long long arr[200100][3];
int from[200100][2];
int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			scanf("%lld", &arr[i][j]);
		}
	}
	dy[0][0] = arr[0][0];
	dy[0][1] = 0x8000000000000000;
	dy[0][1] /= 2;
	for (int i = 1; i < n; i++) {
		for (int a = 0; a < 2; a++) {
			if (dy[i][0] < dy[i - 1][a] + (arr[i - 1][a + 1] - arr[i - 1][a]) + (arr[i][0])) {
				dy[i][0] = dy[i - 1][a] + (arr[i - 1][a + 1] - arr[i - 1][a]) + (arr[i][0]);
				from[i][0] = a;
			}
			if (dy[i][1] < dy[i - 1][a] + arr[i][1]) {
				dy[i][1] = dy[i - 1][a] + arr[i][1];
				from[i][1] = a;
			}
		}
	}
	int p;

	if (dy[n - 1][0] > dy[n - 1][1]) {
		p = 0;
	}
	else {
		p = 1;
	}
	printf("%lld\n", std::max(dy[n - 1][0], dy[n - 1][1]));
	for (int i = n - 1; i > 0; i--) {
		if (p == 0) {
			G[i].push_back(i - 1);
			in[i - 1]++;
		}
		else {
			G[i - 1].push_back(i);
			in[i]++;
		}
		p = from[i][p];
	}
	std::queue<int> que;
	for (int i = 0; i < n; i++) {
		if (in[i] == 0) {
			que.push(i);
		}
	}
	while (!que.empty()) {
		int idx = que.front();
		printf("%d ", idx + 1);
		que.pop();
		for (int to : G[idx]) {
			in[to]--;
			if (in[to] == 0)que.push(to);
		}
	}
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:13:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
space.cpp:16:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &arr[i][j]);
                             ^

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