Cod sursă (job #803126)

#include <bits/stdc++.h>
using namespace std;
// time with space optimization
int bridgeAndTorch(vector<int>& times) {
    sort(times.begin(), times.end());
    int n = times.size();

    if (n == 1) return times[0];
    if (n == 2) return times[1];
    if (n == 3) return times[0] + times[1] + times[2];

    // Variables to store the minimum crossing 
    // times for the last two calculations
    int prev2 = times[0];
    int prev1 = times[1];
    int curr = times[0] + times[1] + times[2];

    // Calculate minimum crossing time iteratively
    for (int i = 4; i <= n; i++) {
      
        // Case 1: Send two fastest people 
        //first and the fastest one 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];

        // Calculate the minimum crossing
        // time for i people
        curr = min(prev2 + option1, prev2 + option2);

        // Update the values for the 
        // next iteration
        prev2 = prev1;
        prev1 = curr;
    }

    return curr;
}
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;
}