Cod sursa(job #978179)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 28 iulie 2013 06:47:00
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 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;
    int best = 0;
    
    ostream_iterator<int> itOut(cout, " ");
    //copy_n(vec + 1, n + 1, itOut);
    //cout << endl << endl;
    
    dp[3] = vec[1] + vec[2];
    for (int i=2; i<n-1; ++i)
    {
        best = max(best, dp[i-1]);
        dp[i+2] = max(dp[i+1], vec[i] + vec[i+1] + best);
    }
    
    //copy_n(dp, n + 3, itOut);
    //cout << endl << endl;
    
    maxVal = max(maxVal, dp[n]);
    
    best = 0;
    dp[1] = dp[2] = dp[3] = 0;
    for (int i=2; i<n; ++i)
    {
        best = max(best, dp[i-1]);
        dp[i+2] = max(dp[i+1], vec[i] + vec[i+1] + best);
    }
    
    maxVal = max(maxVal, dp[n+1]);
    
    //copy_n(dp, n + 3, itOut);
    //cout << endl << endl;
    
    best = 0;
    dp[1] = dp[2] = dp[3] = dp[4] = 0;
    for (int i=3; i<=n; ++i)
    {
        best = max(best, dp[i-1]);
        dp[i+2] = max(dp[i+1], vec[i] + vec[i+1] + best);
    }
    
    maxVal = max(maxVal, dp[n+2]);
    
    //copy_n(dp, n + 3, itOut);
    //cout << endl << endl;
    
    fout << maxVal << "\n";
    
    return 0;
}