Cod sursa(job #2260666)

Utilizator giotoPopescu Ioan gioto Data 15 octombrie 2018 12:41:52
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <bits/stdc++.h>
using namespace std;

int n;
int a[100005], d[100005][3];
int main()
{
    freopen("oo.in", "r", stdin);
    freopen("oo.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n ; ++i)
        scanf("%d", &a[i]);

    if(n == 2){
        printf("%d", a[1] + a[2]);
        return 0;
    }

    int Sol = 0;

    memset(d, 0, sizeof(d));
    d[1][1] = a[1] + a[2];
    d[2][2] = a[2] + a[3];
    Sol = max(Sol, max(d[1][1], d[2][2]));
    for(int i = 3; i < n - 1 ; ++i){
        d[i][0] = max(d[i - 3][0] + a[i] + a[i + 1], d[i - 1][0]);
        d[i][1] = max(d[i - 3][1] + a[i] + a[i + 1], d[i - 1][1]);
        d[i][2] = max(d[i - 3][2] + a[i] + a[i + 1], d[i - 1][2]);
        Sol = max(max(Sol, d[i][2]), max(d[i][0], d[i][1]));
    }

    if(n > 4){
        int i = n - 1;
        d[i][0] = d[i - 3][0] + a[i] + a[i + 1];
        if(n > 5)
        d[i][2] = d[i - 3][2] + a[i] + a[i + 1];
        Sol = max(max(Sol, d[i][2]), max(d[i][0], d[i][1]));
    }
    if(n > 5){
        int i = n;
        d[i][0] = d[i - 3][0] + a[i] + a[1];
        Sol = max(Sol, d[i][0]);
    }

    printf("%d", Sol);

    return 0;
}