Cod sursa(job #794490)

Utilizator alexalghisiAlghisi Alessandro Paolo alexalghisi Data 6 octombrie 2012 13:39:14
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <algorithm>
using namespace std;

int dp1[200005];
int dp2[200005];
int dp3[200005];
int v[200005];

int main()
{
    int n;
    ifstream f("oo.in");
    ofstream g("oo.out");
    f>>n;
    for(int i=1;i<=n;i++)
        f>>v[i];

    v[n+1]=v[1];

    // caz 1
    dp1[1]=v[1];
    dp1[2]=v[1]+v[2];
    dp1[3]=dp1[2];
    for(int i=4;i<n;i++)
        dp1[i]=max(dp1[i-1],v[i]+v[i-1]+dp1[i-3]);
    //caz 2
    dp2[2]=v[2];
    dp2[3]=v[2]+v[3];
    dp2[4]=dp2[3];
    for(int i=5;i<=n;i++)
        dp2[i]=max(dp2[i-1],v[i]+v[i-1]+dp2[i-3]);

    dp3[n]=v[n];
    dp3[1]=v[n]+v[1];
    dp3[2]=dp3[1];
    for(int i=3;i<n-1;i++)
        dp3[i]=max(dp3[i-1],v[i]+v[i-1]+dp3[i-3]);

    g<< max ( max (*max_element(dp2+1,dp2+n+1),*max_element(dp3+1,dp3+n+1)) , *max_element(dp1+1,dp1+n+1));
    return 0;
}