Submission #20687

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

space

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

int a[3][200001];

long long f(int l, int r, int le, int re, std::vector<int> &res)
{
	if(l==r)
	{
		res.push_back(l);
		return a[le+re][l];
	}

	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)
		{
			res.push_back(l);
			res.push_back(r);
			return t1;
		}
		else
		{
			res.push_back(r);
			res.push_back(l);
			return t2;
		}
	}

	int x = (l+r)/2;
	long long tl0, tl1, tr0, tr1;
	std::vector<int> le0, le1, re0, re1;

	tl0 = f(l, x-1, le, 0, le0);
	tl1 = f(l, x-1, le, 1, le1);
	tr0 = f(x+1, r, 0, re, re0);
	tr1 = f(x+1, r, 1, re, re1);

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

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

	if(p1 == pm)
	{
		res.push_back(x);
		res.insert(res.end(), le0.begin(), le0.end());
		res.insert(res.end(), re0.begin(), re0.end());
	}
	else if(p2 == pm)
	{
		res.insert(res.end(), le1.begin(), le1.end());
		res.push_back(x);
		res.insert(res.end(), re0.begin(), re0.end());
	}
	else if(p3 == pm)
	{
		res.insert(res.end(), le1.begin(), le1.end());
		res.insert(res.end(), re1.begin(), re1.end());
		res.push_back(x);
	}
	else if(p4 == pm)
	{
		res.insert(res.end(), re1.begin(), re1.end());
		res.push_back(x);
		res.insert(res.end(), le0.begin(), le0.end());
	}
	else if(p5 == pm)
	{
		res.insert(res.end(), re1.begin(), re1.end());
		res.insert(res.end(), le1.begin(), le1.end());
		res.push_back(x);
	}

	return pm;
}

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]);

	long long r;
	std::vector<int> res;

	r = f(1, n, 1, 1, res);

	printf("%lld\n", r);
	for(int &v : res)
		printf("%d ", v);
	return 0;
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:89:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
space.cpp:91: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: 0 / 26
• Subtask 5: 0 / 28