Cod sursa(job #2121615)

Utilizator Alex18maiAlex Enache Alex18mai Data 3 februarie 2018 22:17:57
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <fstream>

using namespace std;

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

int val[100100];
int dp[100100][2];

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin>>n;

    for (int i=1; i<=n; i++){
        cin>>val[i];
    }

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

    int st = dp[n][0];

    for (int i=1; i<=n; i++){
        dp[i][0] = 0;
        dp[i][1] = 0;
    }

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

    int dr = dp[1][0];

    for (int i=1; i<=n; i++){
        dp[i][0] = 0;
        dp[i][1] = 0;
    }

    val[0] = val[n];

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

    int mij = dp[n-1][0];

    //cout<<st<<" "<<dr<<" "<<mij<<'\n';

    cout<<max(max(st , dr) , mij);

    return 0;
}