P1809 River Crossing Problem

On a sunny day, Oliver and his classmates, $N$ people in total, come to the east bank of a river and want to cross to the west bank. There is a small boat on the east bank. The boat is very small and can carry at most two people at a time. Each person has a crossing time $T$, and the time of a trip equals the longer crossing time among the people on the boat. Given the crossing times $T$ of all $N$ people, Oliver wants you to tell him the minimum total time needed for everyone to cross the river. Note that only people on the bank where the boat currently is (east or west) may board the boat to row to the other side.

The first line contains the number of people $N$. The next $N$ lines each contain one number. The number on the $(i+1)$-th line is the crossing time of the $i$-th person.

Output a single number, the minimum total time for all people to cross the river.

Constraints For $40\%$ of the testdata, $N \le 8$. For $100\%$ of the testdata, $N \le 10^5, T \le 10^7$. Sample Explanation - Initial: east bank {1, 2, 3, 4}, west bank {}. - First: east bank {3, 4}, west bank {1, 2}, time 7. - Second: east bank {1, 3, 4}, west bank {2}, time 6. - Third: east bank {1}, west bank {2, 3, 4}, time 15. - Fourth: east bank {1, 2}, west bank {3, 4}, time 7. - Fifth: east bank {}, west bank {1, 2, 3, 4}, time 7. So the total time is $7+6+15+7+7=42$, and there is no better plan. Translated by ChatGPT 5