Cod sursă (job #692070)

/*
Avem un numar optim de 2*(n-1)-1 mutari
*/
#include <fstream>
#include <vector>
using namespace std;

ifstream cin("lanterna.in");
ofstream cout("lanterna.out");

int n, total, minim = 1000000000;
vector<int> t(100000 + 10);
bool stanga[100000 + 10];

void citire()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> t[i];
}

bool esteSolutie()
{
	for (int i = 1; i <= n; i++)
		if (stanga[i] == true)
			return false;
	return true;
}

void backtracking(int pas)
{
	if (pas % 2 == 1)
	{
		for(int i = 1;i <= n;i++)
			if(stanga[i] == true)
			for(int j = 1;j <= n;j++)
				if (stanga[j] == true)
				{
					total += max(t[i], t[j]);
					stanga[i] = false;
					stanga[j] = false;
					if (pas == 2 * (n - 1) - 1 && total < minim && esteSolutie())
						minim = total;
					if(pas < 2*(n-1)-1)
						backtracking(pas + 1);
					total -= max(t[i], t[j]);
					stanga[i] = true;
					stanga[j] = true;
				}
	}
	else
	{
		for(int i = 1;i <= n;i++)
			if (stanga[i] == false)
			{
				total += t[i];
				stanga[i] = true;
				if (pas < 2 * (n - 1) - 1)
					backtracking(pas + 1);
				total -= t[i];
				stanga[i] = false;
			}
	}
}

int main()
{
	citire();
	for (int i = 1; i <= n; i++)
		stanga[i] = true;
	backtracking(1);
	cout << minim;
	return 0;
}