Submission #20680

#	Time	Username	Problem	Language	Result	Execution time	Memory
20680		Kwiyomi Express (#35)	Can polan into space? (OJUZ11_space)	C++98	100 / 100	156 ms	25504 KiB

space

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <cmath>
#include <iostream>
#include <sstream>
#include <set>
using namespace std;

int main()
{
	int n;
	cin >> n;
	vector<vector<long long> > cost(n+1, vector<long long>(2));
	vector<vector<long long> > from(n, vector<long long>(2));
	// 0 : me fly early, 1 : me fly late
	cost[0][1] = 0;
	cost[0][0] = -9999999999999999LL;
	for (int i=0; i<n; i++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		cost[i+1][0] = max(cost[i][0] + b, cost[i][1] + a);
		cost[i+1][1] = max(cost[i][0] + c, cost[i][1] + b);
		from[i][0] = (cost[i+1][0] == cost[i][1] + a);
		from[i][1] = (cost[i+1][1] == cost[i][1] + b);
	}
	printf("%lld\n", cost[n][0]);

	vector<int> res(n);
	int idx = 0;
	int ll = 0, rr = 0;
	res[n-1] = 0;
	for (int i=n-1; i>=1; i--) {
		if (from[i][idx] == 1) {
			rr ++;
			res[i-1] = rr;
			idx = 1;
		} else {
			ll --;
			res[i-1] = ll;
			idx = 0;
		}
	}
	vector<int> ret(n);
	for (int i=0; i<n; i++) ret[res[i]-ll] = i+1;

	for (int i=0; i<n; i++)
		printf("%d ", ret[i]);
	printf("\n");
}

Compilation message (stderr)

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

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