Cod sursa(job #2121629)

Utilizator Alex18maiAlex Enache Alex18mai Data 3 februarie 2018 22:37:46
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.9 kb
#include <fstream>

using namespace std;

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

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

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];
    }

    val[n+1] = val[1];
    val[n+2] = val[2];

    int ans = val[1] + val[2];

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

    dp[3] = 0;

    //cout<<dp[n]<<'\n';

    ans = max(ans , dp[n]);

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

    //cout<<dp[n + 1]<<'\n';

    ans = max(ans , dp[n+1]);

    dp[4] = 0;

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

    //cout<<dp[n + 2]<<'\n';

    ans = max(ans , dp[n+2]);

    cout<<ans;

    return 0;
}