Cod sursa(job #2749130)

Utilizator mariusn01Marius Nicoli mariusn01 Data 5 mai 2021 10:26:02
Problema Oo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <fstream>

using namespace std;
int v[100010];
int n, sol, i;
int greedy(int st, int dr) {
    /// determin suma maxima alegnd cate doua valori vecine din secventa cu indici
    /// de la st la dr inclusiv
    int rez = 0;
    int f[100010] = {0};
    for (int i=1;i<=n;i++)
        f[i] = 0; /// niciun element din v nu a fost ales;

    for (;;) {
        /// caut in v 2 elemente vecine care pot fi alese si iau perechea cu
        /// suma maxima dintre cele cu aceasta proprietate (conform alg greedy hotarat)
        int maxim = -1, poz;
        for (int i=st;i<dr;i++)
            if (f[i] == 0 && f[i+1] == 0 && v[i] + v[i+1] > maxim) {
                maxim = v[i] + v[i+1];
                poz = i;
            }
        if (maxim != -1) {
            rez += maxim;
            f[poz] = 1;
            f[poz+1] = 1;
            f[poz-1] = 1;
            f[poz+2] = 1; /// elementele de pe aceste pozitii le marchez ca nu mai pot
                        /// fi alese
        } else
            break;
    }
    return rez;
}

int main () {
    ifstream fin ("oo.in");
    ofstream fout("oo.out");

    fin>>n;
    for (i=1;i<=n;i++) {
        fin>>v[i];
    }
/**
    Cazul 1 nu aleg pe primul
    Am un sir care nu e circular cu pozitii de la 2 la n si trebuie sa aleg perechi
    de cate 2
**/

/**
    Cazul 2 nu aleg pe ultimul
    Am un sir care nu e circular cu pozitii de la 1 la n-1 si trebuie sa aleg perechi
    de cate 2
**/

/**
    Cazul 3 aleg pe primul si pe ultimul
    Am un sir care nu e circular cu pozitii de la 3 la n-2 si trebuie sa aleg perechi
    de cate 2
**/
    sol = greedy(2, n);
    sol = max(sol, greedy(1, n-1));
    sol = max(sol, greedy(3, n-2) + v[1] + v[n]);
    fout<<sol;
    return 0;
}