Submission #20697

#	Time	Username	Problem	Language	Result	Execution time	Memory
20697		alex9801 == gs13105 (#35)	Can polan into space? (OJUZ11_space)	C++14	100 / 100	156 ms	28036 KiB

space

#include <stdio.h>
#include <string.h>
#include <algorithm>

int a[3][200001];

long long m1[4][524300];
int m2[4][524300];

void f(int h, int l, int r, int le, int re)
{
	int q = le*2 + re;

	if(m1[q][h])
		return;

	if(l==r)
	{
		m1[q][h] = a[le+re][l];
		m2[q][h] = 0;
		return;
	}

	if(l+1 == r)
	{
		int t1 = a[le+1][l] + a[re][r];
		int t2 = a[le][l] + a[re+1][r];

		if(t1 >= t2)
		{
			m1[q][h] = t1;
			m2[q][h] = -1;
		}
		else
		{
			m1[q][h] = t2;
			m2[q][h] = -2;
		}
		return;
	}

	int x = (l+r)/2;

	f(2*h, l, x-1, le, 0);
	f(2*h, l, x-1, le, 1);
	f(2*h+1, x+1, r, 0, re);
	f(2*h+1, x+1, r, 1, re);

	long long tl0 = m1[2*le][2*h];
	long long tl1 = m1[2*le+1][2*h];
	long long tr0 = m1[re][2*h+1];
	long long tr1 = m1[2+re][2*h+1];

	long long p1 = a[2][x] + tl0 + tr0;
	long long p2 = a[1][x] + tl1 + tr0;
	long long p3 = a[0][x] + tl1 + tr1;
	long long p4 = a[1][x] + tl0 + tr1;
	long long p5 = a[0][x] + tl1 + tr1;

	long long pm = std::max({p1, p2, p3, p4, p5});

	m1[q][h] = pm;

	if(p1 == pm)
		m2[q][h] = 1;
	else if(p2 == pm)
		m2[q][h] = 2;
	else if(p3 == pm)
		m2[q][h] = 3;
	else if(p4 == pm)
		m2[q][h] = 4;
	else if(p5 == pm)
		m2[q][h] = 5;
}

void g(int h, int l, int r, int le, int re)
{
	int q = le*2 + re;
	int x = (l+r)/2;

	switch(m2[q][h])
	{
	case 0:
		printf("%d ", l);
		break;
	case -1:
		printf("%d %d ", l, r);
		break;
	case -2:
		printf("%d %d ", r, l);
		break;
	case 1:
		printf("%d ", x);
		g(2*h, l, x-1, le, 0);
		g(2*h+1, x+1, r, 0, re);
		break;
	case 2:
		g(2*h, l, x-1, le, 1);
		printf("%d ", x);
		g(2*h+1, x+1, r, 0, re);
		break;
	case 3:
		g(2*h, l, x-1, le, 1);
		g(2*h+1, x+1, r, 1, re);
		printf("%d ", x);
		break;
	case 4:
		g(2*h+1, x+1, r, 1, re);
		printf("%d ", x);
		g(2*h, l, x-1, le, 0);
		break;
	case 5:
		g(2*h+1, x+1, r, 1, re);
		g(2*h, l, x-1, le, 1);
		printf("%d ", x);
		break;
	}
}

int main()
{
	int n, i;
	scanf("%d", &n);
	for(i = 1; i<=n; i++)
		scanf("%d%d%d", &a[2][i], &a[1][i], &a[0][i]);

	f(1, 1, n, 1, 1);

	printf("%lld\n", m1[3][1]);

	g(1, 1, n, 1, 1);
	
	return 0;
}

Compilation message (stderr)

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

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