Cod sursă (job #803121)

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

int minCrossingTime(vector<int>& times, 
                    int n, vector<int>& memo) {
    if (n == 1) return times[0];
    if (n == 2) return times[1];
    if (n == 3) return times[0] + times[1] + times[2];
  
    if (memo[n] != -1) return memo[n];

    int option1 = times[1] + times[0] 
                          + times[n - 1] + times[1];

    int option2 = times[n - 1] + times[0] 
                            + times[n - 2] + times[0];

    int result = min(option1 + minCrossingTime(times, n - 2, memo),
                 option2 + minCrossingTime(times, n - 2, memo));

    memo[n] = result;
    return result;
}

int bridgeAndTorch(vector<int>& times) {
    sort(times.begin(), times.end());
    int n = times.size();
    vector<int> memo(n + 1, -1); 
    return minCrossingTime(times, n, memo);
}

int main() {
    freopen("lanterna.in", "r", stdin);
    freopen("lanterna.out", "w", stdout);
    int n; cin>>n;
    vector<int> times (n);
    for(int i = 0; i < n; i++)
      cin>>times[i];
    cout << bridgeAndTorch(times);
    return 0;
}