Cod sursa(job #978175)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 28 iulie 2013 05:36:49
Problema Oo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <fstream>
#include <iostream>
#include <iterator>
#include <algorithm>

#define MAXN 100006

using namespace std;

int vec[MAXN];

int dp[MAXN];

int main()
{
    int n;
    fstream fin("oo.in", fstream::in);
    fstream fout("oo.out", fstream::out);
    
    fin >> n;
    //cout << n << endl;
    
    for (int i=1; i<=n; ++i)
    {
        fin >> vec[i];
    }
    
    vec[n + 1] = vec[1];
    
    int maxVal = 0;
    
    ostream_iterator<int> itOut(cout, " ");
    //copy_n(vec + 1, n + 1, itOut);
    //cout << endl << endl;
    
    for (int i=1; i<n-1; ++i)
    {
        dp[i+2] = max(dp[i+1], vec[i] + vec[i+1] + dp[i-1]);
    }
    
    //copy_n(dp, n + 3, itOut);
    //cout << endl << endl;
    
    maxVal = max(maxVal, dp[n]);
    
    dp[1] = dp[2] = dp[3] = 0;
    for (int i=2; i<n; ++i)
    {
        dp[i+2] = max(dp[i+1], vec[i] + vec[i+1] + dp[i-1]);
    }
    
    maxVal = max(maxVal, dp[n+1]);
    
    //copy_n(dp, n + 3, itOut);
    //cout << endl << endl;
    
    dp[1] = dp[2] = dp[3] = dp[4] = 0;
    for (int i=3; i<=n; ++i)
    {
        dp[i+2] = max(dp[i+1], vec[i] + vec[i+1] + dp[i-1]);
    }
    
    maxVal = max(maxVal, dp[n+1]);
    
    //copy_n(dp, n + 3, itOut);
    //cout << endl << endl;
    
    fout << maxVal << "\n";
    
    return 0;
}