Cod sursă (job #15017)

#include <vector>
#include <algorithm>
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("lanterna.in");
ofstream g("lanterna.out");

long long n;

vector <int> v;

bool dr[100009];
long long nr,min_st, min_st2, min_dr, max_st,max_st2,timp;

void citire()
{
    int x;
    f>>n;
    for( int i=0;i<n;i++)
    {
        f>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
}

void proces()
{
    timp+=v[1]+v[0];
    dr[1]=true;
    nr=1;
    min_st = 0;
    min_st2 = 2;
    min_dr = 1;
    max_st = n-1;
    max_st2 = n-2;

    while(nr<n-2)
    {
        if(v[max_st] + v[max_st2] - v[min_dr] > v[min_st] + v[max_st])
        {
            timp += v[max_st] + v[min_dr];
            dr[max_st] = true;
            dr[max_st2] = true;
            dr[min_dr] = false;
            max_st = max_st-2;
            max_st2 = max_st2-2;

            if(min_dr < min_st2) {
                min_st2 = min_dr;
            }

            for( int i=0;i<n;i++)
            {
                if(dr[i]) {
                    min_dr =i;
                    break;
                }
            }
        } else if(v[min_st]+v[min_st2]*2+v[max_st] < v[min_st]*2 + v[max_st] + v[max_st2]) {
            dr[min_st2]=true;
            timp += v[min_st] + v[min_st2];
            if(min_st2 < min_dr) {
                min_dr = min_st2;
            }
            for( int i=min_st+1;i<n;i++)
            {
                if(!dr[i]) {
                    min_st2 = i;
                    break;
                }
            }
        } else {
            timp += v[max_st] + v[min_st];
            dr[max_st] = true;
            max_st = max_st-1;
            max_st2 = max_st2-1;
        }
        nr++;
    }
    for( int i=min_st+1;i<n;i++)
    {
        if(!dr[i]) {
            timp += v[i];
            break;
        }
    }
    g<<timp;
}

int main()
{
    citire();
    proces();
    return 0;
}