Cod sursa(job #1094133)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 28 ianuarie 2014 22:12:39
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.73 kb
#include <fstream>

using namespace std;

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

int dp[100001],a[100001],s[100001];
int maxv,n;

void DP (int i, int n)
{
    for (; i<=n; ++i)
    {
        dp[i] = max (dp[i-3]+s[i],dp[i-1]);
    }
    maxv = max (maxv,dp[n]);
}

int main()
{
    fin>>n;

    for (int i=1; i<=n; ++i)
    {
        fin>>a[i];
    }

    for (int i=1; i<n; ++i)
    {
        s[i] = a[i] + a[i+1];
    }
    s[n] = a[n] + a[1];

    dp[1] = s[1];
    dp[2] = max(s[1],s[2]);
    DP(3,n-2);

    dp[1] = 0;
    dp[2] = s[2];
    dp[3] = max (s[2],s[3]);
    DP (4,n-1);


    dp[2] = 0;
    dp[3] = s[3];
    dp[4] = max (s[3],s[4]);
    DP (5,n);

    fout<<maxv;
}