Cod sursa(job #896938)

Utilizator informatician28Andrei Dinu informatician28 Data 27 februarie 2013 18:05:45
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <fstream>

using namespace std;

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

#define n 100001

int N, V[n], dp[n], Sol;

int maxim (int a, int b)
{
    return (a > b) ? a : b;
}

int main()
{
    int i;
    in >> N;
    for (i = 1; i <= N; i++) in >> V[i];
    // iau 1 si 2
    dp[2] = dp[3] = dp[4] = V[1] + V[2];
    for (i = 5; i <= N - 1; i++)
    {
        dp[i] = maxim (dp[i - 1], dp[i - 3] + V[i - 1] + V[i]);
    }
    if (dp[N - 1] > Sol) Sol = dp[N - 1];
    // nu iau 1 si 2
    dp[0] = dp[1] = dp[2] = 0;
    for (i = 3; i <= N; i++)
    {
        dp[i] = maxim (dp[i - 1], dp[i - 3] + V[i - 1] + V[i]);
    }
    if (dp[N] > Sol) Sol = dp[N];
    // iau 1 si N
    dp[1] = dp[2] = dp[3] = V[N] + V[1];
    for (i = 4; i <= N - 2; i++)
    {
        dp[i] = maxim (dp[i - 1], dp[i - 3] + V[i - 1] + V[i]);
    }
    if (dp[N - 2] > Sol) Sol = dp[N - 2];
    out << Sol;
    return 0;
}