Cod sursa(job #34162)

Utilizator filipbFilip Cristian Buruiana filipb Data 20 martie 2007 12:00:29
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <stdio.h>
#define NMax 100005
#define INF 900000000

int N, v[NMax], A[NMax], bst;

int main(void)
{
    int i;
    
    freopen("oo.in", "r", stdin);
    freopen("oo.out", "w", stdout);    
    
    scanf("%d", &N);
    for (i = 1; i <= N; i++)
        scanf("%d", &v[i]);
        
    // alegem primul sector - 1 + 2
    A[0] = A[1] = -INF; A[2] = v[1] + v[2];
    for (i = 3; i < N; i++)
    {
        A[i] = A[i-1];
        if (v[i] + v[i-1] + A[i-3] > A[i])
           A[i] = v[i] + v[i-1] + A[i-3];
    }
    bst = A[N-1];

    // alegem primul sector - 1 + N
    A[0] = -INF; A[1] = v[1] + v[N]; A[2] = A[1];
    for (i = 3; i <= N-2; i++)
    {
        A[i] = A[i-1];
        if (v[i] + v[i-1] + A[i-3] > A[i])
           A[i] = v[i] + v[i-1] + A[i-3];
    }
    if (A[N-2] > bst) bst = A[N-2];
    
    // nu alegem primul sector
    A[0] = A[1] = A[2] = 0;
    for (i = 3; i <= N; i++)
    {
        A[i] = A[i-1];
        if (v[i] + v[i-1] + A[i-3] > A[i])
           A[i] = v[i] + v[i-1] + A[i-3];
    }
    if (A[N] > bst) bst = A[N];
        
    printf("%d\n", bst);
       
    return 0;
}