Cod sursă (job #691959)

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

short n, masca, mascaStanga;
vector<short> t(100000 + 10);
short dp[1 << 20][2];

int cautare(int mascaStanga, bool tura)
{
	if (!mascaStanga)
		return 0;
	int& rezultat = dp[mascaStanga][tura];
	//Daca rezultatul acestei subprobleme a fost deja calculat atunci se returneaza rezultatul
	if (~rezultat)
		return rezultat;
	int mascaDreapta = ((1 << n) - 1) ^ mascaStanga;
	if (tura == true)
	{
		//In aceasta tura trebuie sa aducem lantrena de la dreapta la stanga
		int minim = 1000000000, persoana;
		for (int i = 0; i < n; i++)
			if (mascaDreapta & (1 << i) && t[i] < minim)
			{
				minim = t[i];
				persoana = i;
			}
		rezultat = minim + cautare(mascaStanga | (1 << persoana), !tura);
	}
	else if (tura == false)
	{
		//In aceasta tura trebuie sa aducem lanterna de la stanga la dreapta impreuna cu cele 2 persoane
		//Daca in stanga mai este doar o persoana
		if (__builtin_popcount(mascaStanga) == 1)
		{
			for (int i = 0; i < n; i++)
				if (mascaStanga & (1 << i))
				{
					rezultat = t[i];
					break;
				}
		}
		else
		{
			rezultat = 1000000000;
			for (int i = 0; i < n; i++)
			{
				if (!(mascaStanga & (1 << i)))
					continue;
				for (int j = i + 1; j < n; j++)
				{
					if (mascaStanga & (1 << j))
					{
						int valoare = max(t[i], t[j]);
						valoare += cautare(mascaStanga ^ (1 << i) ^ (1 << j), !tura);
						if (valoare < rezultat)
							rezultat = valoare;
					}
				}
			}
		}
	}
	return rezultat;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> t[i];
	masca = (1 << n) - 1;
	memset(dp, -1, sizeof(dp));
	cout << cautare(masca, 0);
	return 0;
}