Cod sursa(job #34159)

Utilizator filipbFilip Cristian Buruiana filipb Data 20 martie 2007 11:54:02
Problema Oo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 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]);
    v[N+1] = v[1];
        
    // alegem primul sector
    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];
    
    // nu alegem primul sector
    A[0] = A[1] = A[2] = 0;
    for (i = 3; i <= N+1; 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+1] > bst) bst = A[N+1];
    
    printf("%d\n", bst);
    
    return 0;
}