Cod sursa(job #1407696)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 29 martie 2015 19:20:12
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.68 kb
#include<fstream>
#include<iostream>
#include<algorithm>
#define oo -1000000000

using namespace std;

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

int a[100005], dp[100005];
int n, maxi = oo;

void citire()
{
    int i;
    f>>n;
    for(i=1; i<=n; i++)
        f>>a[i];
    a[0] = a[n];
    a[n+1] = a[1];
}

void dinam(int st)
{
    dp[st] = oo;
    dp[st+1] = a[st] + a[st + 1];
    dp[st+2] = dp[st+1];

    for(int i= st+3; i<n+st-1; i++)
    {
        dp[i] = max(dp[i-1], dp[i-3] + a[i-1] + a[i]);
    }

    maxi = max(maxi, dp[n+st-2]);
}

int main()
{
    citire();
    dinam(0);
    dinam(1);
    dinam(2);
    g<<maxi<<"\n";
    return 0;
}