Cod sursa(job #3288814)

Utilizator Victor5539Tanase Victor Victor5539 Data 24 martie 2025 13:03:31
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <iostream>
#include <fstream>
#define int long long
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");

const int MAX=1e5;
int v[MAX+5],i,n,ans,dp[MAX+5][5];

int dinamica(int l, int r)
{
    if (l>r)
        return -2e9;

    int i;

    for (i=l; i<=r; i++)
    {
        dp[i][0]=0;
        dp[i][1]=0;
    }

    dp[l+1][1]=v[l]+v[l+1];

    for (i=l+2; i<=r; i++)
    {
        dp[i][1]=v[i]+v[i-1]+dp[i-2][0];
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
    }

    return max(dp[r][0],dp[r][1]);
}

signed main()
{
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i];


    if (n==2)
    {
        fout<<v[1]+v[2];
        return 0;
    }

    ans=max(v[1]+v[n]+dinamica(3,n-2),0LL);
    ans=max(ans,v[1]+v[2]+dinamica(4,n-1));
    ans=max(ans,v[n-1]+v[n]+dinamica(2,n-3));

    fout<<ans;


    return 0;
}