Cod sursa(job #3261774)

Utilizator PiciuAndreiAlinPiciu Andrei Alin PiciuAndreiAlin Data 7 decembrie 2024 11:46:26
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>
using namespace std;


/**
10
a = 3  4  0  1  0  6  7  1  2  1
b = 0  7  7  7  8 13 20 20 20  0
c = 4  4  4  5  5 10
d = 4  4                       4
b[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[1]+a[2]
c[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[1]+a[n]
d[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[n-1]+a[n]
e[i] = suma maxima obtinuta din primele i, alegand obligatoriu a[2]+a[3]

*/
ifstream fin("oo.in");
ofstream fout("oo.out");
int a[100002], b[100002], c[100002], d[100002], e[100002],  n;

int main()
{
    int i, mx;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    /// b:
    b[1] = 0;
    b[3] = b[4] = b[2] = a[1] + a[2];
    for (i = 5; i < n; i++)
    {
        b[i] = b[i - 1];
        if (b[i] < a[i] + a[i - 1] + b[i - 3])
            b[i] = a[i] + a[i - 1] + b[i - 3];
    }
    /// c:
    c[1] = c[2] = c[3] = a[1] + a[n];
    for (i = 4; i <= n - 2; i++)
    {
        c[i] = c[i - 1];
        if (c[i] < a[i] + a[i - 1] + c[i - 3])
            c[i] = a[i] + a[i - 1] + c[i - 3];
    }
    /// d:
    d[n] = d[1] = d[2] = a[n] + a[n - 1];
    for (i = 3; i <= n - 3; i++)
    {
        d[i] = d[i - 1];
        if (d[i] < a[i] + a[i - 1] + d[i - 3])
            d[i] = a[i] + a[i - 1] + d[i - 3];
    }
    /// d:
    e[1] = e[2] = 0;
    e[3] = e[4] = a[2] + a[3];
    for (i = 5; i <= n; i++)
    {
        e[i] = e[i - 1];
        if (e[i] < a[i] + a[i - 1] + e[i - 3])
            e[i] = a[i] + a[i - 1] + e[i - 3];
    }
    /// sol: max(b[n-1], c[n-2], d[n-3], e[n])
    mx = max({b[n - 1], c[n-2], e[n]});
    fout << mx << "\n";
    return 0;
}