Cod sursa(job #2152253)

Utilizator radiogard1999Dragoi Andrei radiogard1999 Data 5 martie 2018 13:12:09
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <bits/stdc++.h>
#define Nmax 100005
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int n,v[Nmax],dp[Nmax][2],sol;
void Citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[(i+3)];
    fin.close();
    v[n+1]=v[1];
    v[n+2]=v[2];
    v[n+3]=v[3];
}
inline void Reset()
{
    int i;
    for(i=1;i<=(n+4);i++)
        dp[i][1]=dp[i][0]=1;
}
void Rezolvare()
{
    int i;
    ///poz1
    dp[2][1]=v[1]+v[2];
    for(i=3;i<=n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
    }
    sol=max(dp[n][1],dp[n][0]);
    Reset();
    ///poz2
    dp[3][1]=v[2]+v[3];
    for(i=4;i<=(n);i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
    }
    sol=max(sol,max(dp[n+1][1],dp[n+1][0]));
    Reset();
    ///poz3
    dp[4][1]=v[3]+v[4];
    for(i=5;i<=(n+1);i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
    }
    sol=max(sol,max(dp[n+2][1],dp[n+2][0]));
    Reset();
    fout<<sol<<"\n";
    fout.close();
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}