Cod sursa(job #3288791)

Utilizator amunnumeVlad Patrascu amunnume Data 24 martie 2025 12:13:21
Problema Oo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>
#include <iostream>
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
const int N=1e5+5;
int n,i,j,v[N],d[N][2];
int solve(int l,int r)
{
    if(l>r) return -2e9;
    for(int i=l;i<=r;++i) d[i][0]=d[i][1]=0;
    d[l+1][1]=v[l]+v[l+1];
    for(int i=l+2;i<=r;++i)
    {
        d[i][1]=d[i-2][0]+v[i-1]+v[i];
        d[i][0]=max(d[i-1][0],d[i-1][1]);
    }
    if(r==n && 3<=n-2) d[r][1]=0;
    return max(d[r][0],d[r][1]);
}
int main()
{
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>v[i];
    }
    fout<<max(solve(1,n),solve(3,n-2)+v[1]+v[n]);
    return 0;
}