Cod sursa(job #2489716)

Utilizator stefan1anubystefan popa stefan1anuby Data 9 noiembrie 2019 11:28:10
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("oo.in");
ofstream cout("oo.out");
int dp[100003],a[100003],n;
/// dp[i] = suma maxima obtinuta din primele i numere
/// dp[i] =max(dp[i-1],dp[i-2], 0);

int main()
{
    int i,M;
    cin>>n;
    for(i=1; i<=n; i++)
    {
        cin>>a[i];
    }
    /// aleg obligatoriu pe a[1]+a[2]
    dp[1]=0;
    dp[2]=a[1]+a[2];
    dp[3]=dp[2];
    dp[4]=dp[3];
    for(i=5; i<n; i++)
    {
        dp[i]=max(dp[i-1],a[i]+a[i-1]+dp[i-3]);
    }
    M=dp[n-1];

    /// aleg obligatoriu pe a[2]+a[3]

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

    /// aleg obligatoriu pe a[1]+a[n]
    dp[1]=a[1]+a[n];
    dp[2]=dp[3]=dp[1];
    for(i=4; i<=n-2; i++)
        dp[i]=max(dp[i-1],a[i]+a[i-1]+dp[i-3]);
    M=max(M,dp[n-2]);
    cout<<M;
    return 0;
}