Cod sursa(job #2489718)

Utilizator Gabi303valentin gabriel Gabi303 Data 9 noiembrie 2019 11:28:44
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <algorithm>

using namespace std;

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

int dp[100005], a[100005], n;

int main()
{
    int i, maxi;
    fin >> n;
    for (i = 1; i <= n; i++)
        fin >> a[i];
    ///aleg pe 1 si pe 2
    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]);
    maxi = dp[n - 1];
    ///aleg pe 2 si 3
    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]);
    maxi = max(maxi, dp[n]);
    ///aleg pe 1 si n
    dp[1] = a[1] + a[n];
    dp[2] = dp[3] = dp[1];
    for (i = 4; i < n - 1; i++)
       dp[i] = max (dp[i - 1],
                     a[i] + a[i - 1] + dp[i - 3]);
    maxi = max(maxi, dp[n - 2]);
    fout << maxi << "\n";
    return 0;
}