Cod sursa(job #1994825)

Utilizator netfreeAndrei Muntean netfree Data 26 iunie 2017 11:09:44
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N_MAX = 100000 + 5;

int ans, n, dp[N_MAX], x[N_MAX];

int solve (int lo, int hi){
    for(int i = lo; i<=hi; ++i)
        dp[i] = 0;

    dp[lo+1] = x[lo] + x[lo+1];
    for(int i = lo+ 2; i<=hi; ++i)
        dp[i] = max(dp[i-1], dp[i-3]+x[i-1]+x[i]);

    return dp[hi];
}

int main()
{
    fin >> n;
    for(int i = 1; i<=n; ++i)
        fin >> x[i];
    x[n+1] = x[1];
    x[0] = x[n];
    ans = max( ans, solve(1,n-1));
    ans = max( ans, solve(2,n));
    ans = max( ans, solve(3,n+1));
    fout << ans;
    return 0;
}