Cod sursa(job #2489715)

Utilizator ParutixLungeanu Razvan Parutix Data 9 noiembrie 2019 11:27:42
Problema Oo Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.07 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("oo.in");
ofstream fout("oo.out");

/// a = 3 4 0 1 0  6  7  1  2 1
/// dp= 0 7 7 7 8 13 20 20 20

int N, DP[100001] , A[100001];

int main()
{
    int i , X , M;
    fin >> N;
    for(i = 1 ; i <= N ; ++i)
        fin >> A[i];

    /// Aleg obligatoriu pe A[1] + A[2]
    DP[1] = 0;
    DP[2] = A[1] + A[2];
    DP[3] = DP[2];
    DP[4] = DP[3];
    for(i = 5 ; i < N ; ++i)
    {
        DP[i] = max(DP[i - 1] , A[i] + A[i - 1] + DP[i - 3]);
    }
    M = DP[N - 1];

    /// Aleg obligatoriu pe A[2] + A[3]
    DP[1] = 0;
    DP[2] = 0;
    DP[3] = A[2] + A[3];
    DP[4] = DP[5] - DP[3];
    for(i = 6 ; i <= N ; ++i)
    {
        DP[i] = max(DP[i - 1] , A[i] + A[i - 1] + DP[i - 3]);
    }
    M = max(M , DP[N]);

    /// Aleg obligatoriu pe A[1] + A[N]
    DP[1] = A[1] + A[N];
    DP[2] = DP[3] = DP[1];
    for(i = 4 ; i <= N - 2 ; ++i)
    {
        DP[i] = max(DP[i - 1] , A[i] + A[i - 1] + DP[i - 3]);
    }
    M = max(M , DP[N - 2]);

    fout << M;

    return 0;
}