Cod sursa(job #2697072)

Utilizator As932Stanciu Andreea As932 Data 17 ianuarie 2021 17:11:39
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
///#include <iostream>
#include <algorithm>

using namespace std;

ifstream cin("oo.in");
ofstream cout("oo.out");

const int nmax = 1e5 + 5;

int n, v[nmax], dp[nmax];

void read(){
    cin >> n;

    for(int i = 1; i <= n; i++)
        cin >> v[i];

    v[n + 1] = v[1];
}

int tryDP(int l, int r){
    dp[l] = 0;
    dp[l + 1] = v[l] + v[l + 1];

    for(int i = l + 2; i <= r; i++)
        dp[i] = max(dp[i - 1], dp[i - 3] + v[i] + v[i - 1]);

    return dp[r];
}

void solve(){
    int p1 = tryDP(1, n - 1);
    int p2 = tryDP(2, n);
    int p3 = tryDP(3, n + 1);

    cout << max({p1, p2, p3});
}

int main()
{
    read();
    solve();

    return 0;
}