Cod sursă (job #692073)

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

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

int solveBridgeAndTorchProblem(int mask, bool tura, vector<int>& t, vector<vector<int>>& dp)
{
    int n = t.size();
    // if nobody is left to transfer
    if (!mask)
        return 0;
    if (dp[mask][tura] != -1)
        return dp[mask][tura];
    int rightMask = ((1 << n) - 1) ^ mask;
    int rezultat = 0;
    // transfer people from left to right (from destination to start)
    if (tura == 1) {
        int minim = INT_MAX, persoana;
        for (int i = 0; i < n; ++i) {
            // choose the persoana with smallest time to cross bridge
            if (rightMask & (1 << i)) {
                if (minim > t[i]) {
                    persoana = i;
                    minim = t[i];
                }
            }
        }
        // now send this persoana to let and solve for smaller problem
        rezultat = t[persoana] + solveBridgeAndTorchProblem(mask | (1 << persoana), tura ^ 1, t, dp);
    }
    else {
        // __builtin_popcount() counts the bits in mask
        if (__builtin_popcount(mask) == 1) {
            for (int i = 0; i < n; ++i) {
                // since there is only a single persoana on starting side, return him
                if (mask & (1 << i)) {
                    rezultat = t[i];
                    break;
                }
            }
        }
        else {
            // find the minimum time by solving for each pair
            rezultat = INT_MAX;
            for (int i = 0; i < n; ++i) {
                // if ith persoana is not on right side, then do nothing
                if (!(mask & (1 << i)))
                    continue;
                // else find another persoana and try to cross the bridge
                for (int j = i + 1; j < n; ++j) {
                    if (mask & (1 << j)) {
                        // time to cross the bridge for current pair
                        int valoare = max(t[i], t[j]);
                        // solve for smaller subproblems
                        valoare += solveBridgeAndTorchProblem(mask ^ (1 << i) ^ (1 << j), tura ^ 1, t, dp);
                        // update the answer
                        rezultat = min(rezultat, valoare);
                    }
                }
            }
        }
    }
    return dp[mask][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 mask = (1 << n) - 1;
    cout << solveBridgeAndTorchProblem(mask, 0, t, dp);
    return 0;
}