Cod sursă (job #691962)

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

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

int rezolvare(int masca, bool tura, vector<int>& t, vector<vector<int>>& dp)
{
    int n = t.size();
    if (!masca)
        return 0;
    if (dp[masca][tura] != -1)
        return dp[masca][tura];
    int mascaDreapta = ((1 << n) - 1) ^ masca;
    int rezultat = 0;
    if (tura == 1) {
        int minim = INT_MAX, persoana;
        for (int i = 0; i < n; ++i) {
            if (mascaDreapta & (1 << i)) {
                if (minim > t[i]) {
                    persoana = i;
                    minim = t[i];
                }
            }
        }
        rezultat = t[persoana] + rezolvare(masca | (1 << persoana), tura ^ 1, t, dp);
    }
    else {
        if (__builtin_popcount(masca) == 1) {
            for (int i = 0; i < n; ++i) {
                if (masca & (1 << i)) {
                    rezultat = t[i];
                    break;
                }
            }
        }
        else {
            rezultat = INT_MAX;
            for (int i = 0; i < n; ++i) {
                if (!(masca & (1 << i)))
                    continue;
                for (int j = i + 1; j < n; ++j) {
                    if (masca & (1 << j)) {
                        int val = max(t[i], t[j]);
                        val += rezolvare(masca ^ (1 << i) ^ (1 << j), tura ^ 1, t, dp);
                        rezultat = min(rezultat, val);
                    }
                }
            }
        }
    }
    return dp[masca][tura] = rezultat;
}
int main()
{
    int n; cin >> n;
    vector<int> t(n);
    for (int i = 0; i < n; i++)cin >> t[i];
    vector<vector<int>> dp(1 << 20, vector<int>(2, -1));
    int masca = (1 << n) - 1;
    cout << rezolvare(masca, 0, t, dp);
    return 0;
}