Cod sursă (job #692080)

/*
Avem un numar optim de 2*(n-1)-1 mutari
*/
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

int n;
vector<int> t;

void citire()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		long long int x;
		cin >> x;
		t.push_back(x);
	}
}

int main()
{
	citire();
	sort(t.begin(), t.end());
	if (n == 0)
		cout << 0;
	else if (n == 1)
		cout << t[0];
	else if (n == 2)
		cout << t[1];
	else
	{
		long long int suma = 0;
		for (int i = 1; i < n; i++)
			suma += t[i];
		long long int total = (n - 2) * t[0] + suma;
		int x = n;
		long long int auxiliar = 2 * t[1] - t[0];
		while (t[x - 2] > auxiliar)
		{
			total -= t[x - 2] - auxiliar;
			x -= 2;
		}
		cout << total;
	}
	return 0;
}