Cod sursa(job #3245662)

Utilizator paull122Paul Ion paull122 Data 29 septembrie 2024 21:29:08
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <bits/stdc++.h>

#define VMAX 50000
#define NMAX 100005
#define LOG 19
#define INF (long long)(1e18)
#define MOD 1000000009
#define ll long long int

#define ADD 1e9

#define NIL 0



using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");

int dp[NMAX+1][2];
int n;
int a[NMAX+1];

int main()
{
    fin >> n;
    for(int i=1;i<=n;i++)
    {
        fin >> a[i];
    }
    if(n==2)
    {
        fout << a[1]+a[2];
        return 0;
    }
    dp[2][1]=a[1]+a[2];
    dp[3][0]=dp[2][1];
    for(int i=4;i<=n-1;i++)
    {
        dp[i][0]=max(dp[i-1][1],dp[i-1][0]);
        dp[i][1]=a[i]+a[i-1]+dp[i-2][0];
    }
    int res = max(dp[n-1][1],dp[n-1][0]);

    memset(dp,0,sizeof(dp));

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


    res=max(res,max(dp[n][1],dp[n][0]));

    memset(dp,0,sizeof(dp));

    dp[1][1] = a[1]+a[n];
    dp[2][0] = dp[1][1];

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

    res=max(res,max(dp[n-2][1],dp[n-2][0]));

    fout << res;
    /// 7 2 3 4 5


}