Cod sursa(job #1204238)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 iulie 2014 14:06:51
Problema Oo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int Nmax = 100005;

int Values[Nmax];

int Solve(int *begin, int *end)
{
    vector<int> Dp(end - begin + 1, 0);
    Dp[2] = *begin + *(begin + 1);

    for (int *p = begin + 2; p <= end; p++)
        Dp[p - begin + 1] = max(Dp[p - begin], Dp[p - begin - 2] + *(p - 2) + *(p - 1));

    return Dp.back();
}

int main()
{
    freopen("oo.in", "r", stdin);
    freopen("oo.out", "w", stdout);

    int N;
    scanf("%d", &N);

    for (int i = 1; i <= N; i++)
        scanf("%d", &Values[i]);

    if (N == 2)
    {
        printf("%d\n", Values[1] + Values[2]);
        return 0;
    }

    Values[N + 1] = Values[1];
    Values[N + 2] = Values[2];

    printf("%d\n", max(Solve(Values + 3, Values + N + 2), max(Solve(Values + 2, Values + N + 1), Solve(Values + 1, Values + N))));
}