Cod sursa(job #1908506)

Utilizator robx12lnLinca Robert robx12ln Data 7 martie 2017 09:01:50
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.26 kb
#include<fstream>
#include<cstring>
#define DIM 100005
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int D[DIM], v[DIM], n, sol;

int det_max(){
    int maxim = 0;
    for( int i = 1; i <= n; i++ ){
        maxim = max( maxim, D[i] );
    }
    return maxim;
}

int main(){
    fin >> n;
    for( int i = 1; i <= n; i++ ){
        fin >> v[i];
    }
    //iau mereu oua din sectorul i si i+1
    //cazul I : nu am de gand sa iau oua din sectorul n - 1
    D[1] = v[1] + v[2];
    D[2] = max( D[1], v[2] + v[3] );
    for( int i = 3; i <= n - 2; i++ ){
        D[i] = max( D[i - 1], D[i - 3] + v[i] + v[i + 1] );
    }
    sol = max( sol, det_max() );
    //cazul II iau oua din n - 1 deci nu mai pot lua din 1
    memset( D, 0, sizeof(D) );
    D[2] = v[2] + v[3];
    for( int i = 3; i <= n - 1; i++ ){
        D[i] = max( D[i - 1], D[i - 3] + v[i] + v[i + 1] );
    }
    sol = max( sol, det_max() );
    //cazul III iau oua din sectorul n deci nu pot sa mai iau din 2
    memset( D, 0, sizeof(D) );
    v[n + 1] = v[1];
    for( int i = 3; i <= n; i++ ){
        D[i] = max( D[i - 1], D[i - 3] + v[i] + v[i + 1] );
    }
    sol = max( sol, det_max() );
    //afisare solutie
    fout << sol << "\n";
    return 0;
}