Cod sursă (job #803130)

// C++ code for Bridge and Torch problem
// using Tabulation
#include <bits/stdc++.h>
using namespace std;

// Function to calculate minimum crossing 
// time using tabulation
int bridgeAndTorch(vector<int>& times) {
    sort(times.begin(), times.end());
    int n = times.size();

    // Create a dp vector to store minimum crossing 
    // times for each count of people
    vector<int> dp(n + 1, INT_MAX);
    dp[1] = times[0];
    if (n > 1) dp[2] = times[1];
    if (n > 2) dp[3] = times[0] + times[1] + times[2];

    // Fill dp array iteratively for 
    // each count of people
    for (int i = 4; i <= n; i++) {
      
        // Case 1: Send two fastest people first 
        // and the fastest returns
        int option1 = times[1] + times[0] + 
                        times[i - 1] + times[1];
        
        // Case 2: Send two slowest people first
        // and the second fastest returns
        int option2 = times[i - 1] + times[0] 
                       + times[i - 2] + times[0];

        // Minimum time required for i people
        dp[i] = min(dp[i - 2] + option1, 
                         dp[i - 2] + option2);
    }

    return dp[n];
}

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) << endl;
    return 0;
}