Submission #20423

#	Time	Username	Problem	Language	Result	Execution time	Memory
20423		KDH (#35)	Can polan into space? (OJUZ11_space)	C++14	0 / 100	156 ms	30024 KiB

space

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n;
ll a[200010][3], b[200010][3], ldp[200010][2], rdp[200010][2];
int lbx[200010][2], lby[200010][2], rbx[200010][2], rby[200010][2];
ll inf = (1LL << 60);

void cal(ll dp[200010][2], int bx[200010][2], int by[200010][2], ll c[200010][3]){
	dp[0][1] = dp[1][1] = -inf;
    for(int i = 1; i <= n + 1; i++){
        dp[i][0] = dp[i - 1][0] + c[i][1]; bx[i][0] = i - 1; by[i][0] = 0;
        if(i > 1 && dp[i][0] < dp[i - 1][1] + c[i - 2][2] + c[i][1]){
			dp[i][0] = dp[i - 1][1] + c[i - 2][2] + c[i][1];
			bx[i][0] = i - 1; by[i][0] = 1;
		}
		if(i > 1) dp[i][1] = dp[i - 2][0] + c[i][0]; bx[i][1] = i - 2; by[i][1] = 0;
		if(i > 2 && dp[i][1] < dp[i - 2][1] + c[i - 3][2] + c[i][0]){
			dp[i][1] = dp[i - 2][1] + c[i - 3][2] + c[i][0];
			bx[i][1] = i - 2; by[i][1] = 1;
		}
    }
}

void btk(int flag, int bx[200010][2], int by[200010][2], int x, int y){
	if(!x) return;
	btk(flag, bx, by, bx[x][y], by[x][y]);
	for(int i = x - 1; i >= max(1, bx[x][y]); i--) printf("%d ", flag ? n + 1 - i : i);
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < 3; j++){
			scanf("%lld", a[i] + j);
			b[n + 1 - i][j] = a[i][j];
		}
	}
	if(n == 1){
		printf("%lld\n1\n", a[1][0]);
		return 0;
	}
	a[1][2] = a[1][1]; //a[n][2] = a[n][1];
	a[1][1] = a[1][0]; //a[n][1] = a[n][0];
	b[1][2] = b[1][1]; //b[n][2] = b[n][1];
	b[1][1] = b[1][0]; //b[n][1] = b[n][0];
	cal(ldp, lbx, lby, a);
	cal(rdp, rbx, rby, b);
	ll mx = -1, mi;
	for(int i = 1; i <= n; i++){
		//printf("%lld %lld %lld\n", ldp[i][0] - a[i][1], rdp[n + 1 - i][0] - b[n + 1 - i][1], a[i][2]);
		if(mx < (ldp[i][0] - a[i][1]) + (rdp[n + 1 - i][0] - b[n + 1 - i][1]) + a[i][2]){
			mx = (ldp[i][0] - a[i][1]) + (rdp[n + 1 - i][0] - b[n + 1 - i][1] + a[i][2]);
			mi = i;
		}
	}
	printf("%lld\n", mx);
	btk(0, lbx, lby, mi, 0);
	btk(1, rbx, rby, n + 1 - mi, 0);
	printf("%d\n", mi);
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:61:19: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
  printf("%d\n", mi);
                   ^
space.cpp:33:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
space.cpp:36:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", a[i] + j);
                           ^
space.cpp:60:5: warning: 'mi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  btk(1, rbx, rby, n + 1 - mi, 0);
     ^

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