Cod sursa(job #3228133)

Utilizator AswVwsACamburu Luca AswVwsA Data 6 mai 2024 00:08:02
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 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];
int d[NMAX + 1][2];

signed main()
{
    ifstream cin("oo.in");
    ofstream cout("oo.out");
    int n, i;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    int ans = 0;
    //iau primul cu ultimul
    d[1][0] = -1e9;
    d[1][1] = a[1] + a[n];
    d[2][0] = a[1] + a[n];
    d[2][1] = -1e9;
    ans = a[1] + a[n];
    for (i = 3; i <= n - 2; i++)
    {
        d[i][0] = max(d[i - 1][0], d[i - 1][1]);
        d[i][1] = a[i] + a[i - 1] + d[i - 2][0];
        ans = max(ans, max(d[i][0], d[i][1]));
    }
    //nu iau primul cu ultimul
    //iau primii 2
    d[2][0] = -1e9;
    d[2][1] = a[1] + a[2];
    d[3][0] = a[1] + a[2];
    d[3][1] = -1e9;
    ans = max(ans, a[1] + a[2]);
    for (i = 4; i < n; i++)
    {
        d[i][0] = max(d[i - 1][0], d[i - 1][1]);
        d[i][1] = a[i] + a[i - 1] + d[i - 2][0];
        ans = max(ans, max(d[i][0], d[i][1]));
    }
    //iau ultimii 2
    d[1][0] = a[n] + a[n - 1];
    d[1][1] = -1e9;
    d[2][0] = a[n] + a[n - 1];
    d[2][1] = -1e9;
    ans = max(ans, a[n] + a[n - 1]);
    for (i = 3; i <= n - 3; i++)
    {
        d[i][0] = max(d[i - 1][0], d[i - 1][1]);
        d[i][1] = a[i] + a[i - 1] + d[i - 2][0];
        ans = max(ans, max(d[i][0], d[i][1]));
    }
    //nu iau niciunul dintre 1 si n
    d[1][0] = 0;
    d[1][1] = -1e9;
    d[2][0] = 0;
    d[2][1] = -1e9;
    for (i = 3; i < n; i++)
    {
        d[i][0] = max(d[i - 1][0], d[i - 1][1]);
        d[i][1] = a[i] + a[i - 1] + d[i - 2][0];
        ans = max(ans, max(d[i][0], d[i][1]));
    }
    cout << ans;
}