Cod sursa(job #3228128)

Utilizator AswVwsACamburu Luca AswVwsA Data 5 mai 2024 23:32:32
Problema Oo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <climits>
#include <vector>
#include <cassert>
#include <algorithm>
#define ll long long
using namespace std;

const int NMAX = 1e5;

int a[NMAX + 1];

pair <int, pair <int, int> > s[NMAX + 1];

bool viz[NMAX + 1];

int n;

int nxt(int val)
{
    if (val == n)
        return 1;
    return val + 1;
}

int prv(int val)
{
    if (val == 1)
        return n;
    return val - 1;
}

signed main()
{
    ifstream cin("oo.in");
    ofstream cout("oo.out");
    int i, j;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    for (i = 1; i < n; i++)
        s[i] = {a[i] + a[i + 1], {i, i + 1}};
    s[n] = {a[n] + a[1], {1, n}};
    sort(s + 1, s + n + 1, greater <pair <int, pair <int, int> > > ());
    int ans = 0;
    for (i = 1; i <= n; i++)
    {
        int mx = 0;
        int p1, p2;
        for (j = 1; j < n; j++)
            if (!viz[j] and !viz[j + 1] and a[j] + a[j + 1] > mx)
            {
                mx = a[j] + a[j + 1];
                p1 = j;
                p2 = j + 1;
            }
        if (!viz[1] and !viz[n] and a[1] + a[n] > mx)
        {
            mx = a[1] + a[n];
            p1 = 1;
            p2 = n;
        }
        ans += mx;
        viz[p1] = viz[p2] = viz[nxt(p1)] = viz[nxt(p2)] =
        viz[prv(p1)] = viz[prv(p2)] = 1;
    }
    cout << ans;
}