Cod sursa(job #1491032)

Utilizator BLz0rDospra Cristian BLz0r Data 24 septembrie 2015 17:46:17
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define Nmax 100002

FILE *f = fopen ( "oo.in", "r" );
FILE *g = fopen ( "oo.out", "w" );

// D[i] = numarul maxim de oua din primele i cuiburi
int D[Nmax], v[Nmax];

int main(){

    int N, sol = 0;

    fscanf ( f, "%d", &N );

    for ( int i = 1; i <= N; ++i )
        fscanf ( f, "%d", &v[i] );

    //aleg intre a lua ouale din i si i-1 sau nu

    //caz 1: iau ouale 1 si 2
    D[2] = D[3] = D[4] = v[1] + v[2];
    for ( int i = 5; i < N; ++i )
        D[i] = max ( D[i-1], D[i-3] + v[i] + v[i-1] );
    sol = max ( sol, D[N-1] );

    //caz 2: nu iau ouale din 1 si 2
    D[0] = D[1] = D[2] = 0;
    for ( int i = 3; i <= N; ++i )
        D[i] = max ( D[i-1], D[i-3] + v[i] + v[i-1] );
    sol = max ( sol, D[N] );

    //caz 3: iau ouale din 1 si N
    D[1] = D[2] = D[3] = v[1] + v[N];
    for ( int i = 4; i < N-1; ++i )
        D[i] = max ( D[i-1], D[i-3] + v[i] + v[i-1] );
    sol = max ( sol, D[N-2] );

    fprintf ( g, "%d", sol );

    return 0;
}