Submission #20662

#	Time	Username	Problem	Language	Result	Execution time	Memory
20662		우리OJ (#35)	Can polan into space? (OJUZ11_space)	C++14	100 / 100	153 ms	31648 KiB

space

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> Pi;
typedef long long ll;
#define pii Pi
#define pll PL
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> PL;

int N;
int A[200010][3];
ll D[200020][2];
int pre[200020][2];
vector <int> E[200020], v;
int vis[200020];

void dfs(int x){
	vis[x] = 1;
	for(int e : E[x])if(vis[e] == 0)dfs(e);
	v.pb(x);
}

void solve(){
	scanf("%d", &N);
	for(int i=1;i<=N;i++)scanf("%d%d%d", A[i], A[i]+1, A[i]+2);
	if(N == 1){
		printf("%d\n%d\n", A[1][0], 1);
		return;
	}
	D[2][0] = A[2][0] + A[1][1];
	D[2][1] = A[2][1] + A[1][0];
	for(int i=3;i<=N;i++){
		if(D[i-1][0] + A[i-1][1] - A[i-1][0] > D[i-1][1] + A[i-1][2] - A[i-1][1]){
			D[i][0] = D[i-1][0] + A[i-1][1] - A[i-1][0] + A[i][0];
			pre[i][0] = 0;
		}
		else{
			D[i][0] = D[i-1][1] + A[i-1][2] - A[i-1][1] + A[i][0];
			pre[i][0] = 1;
		}
		if(D[i-1][0] > D[i-1][1]){
			D[i][1] = A[i][1] + D[i-1][0];
			pre[i][1] = 0;
		}
		else{
			D[i][1] = D[i-1][1] + A[i][1];
			pre[i][1] = 1;
		}
	}
	int x = 0;
	if(D[N][0] < D[N][1])x = 1;
	printf("%lld\n", D[N][x]);
	for(int i=N;i>1;i--){
		if(x)E[i-1].pb(i);
		else E[i].pb(i-1);
		x = pre[i][x];
	}
	for(int i=1;i<=N;i++)if(vis[i] == 0)dfs(i);
	reverse(all(v));
	for(int e : v)printf("%d ", e); puts("");
}

int main(){
	int Tc = 1; //scanf("%d", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		//printf("Case #%d: ", tc);
		solve();
	}
	return 0;
}

Compilation message (stderr)

space.cpp: In function 'void solve()':
space.cpp:47:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
space.cpp:48:60: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++)scanf("%d%d%d", A[i], 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