Cod sursa(job #1927685)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 15 martie 2017 13:30:11
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <bits/stdc++.h>

#define NMAX 100005

using namespace std;

ifstream f("oo.in");
ofstream g("oo.out");

int N, dp[NMAX], a[NMAX];

int main() {
    f >> N;
    for (int i = 1; i <= N; ++i) {
        f >> a[i];
    }

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

    int ans = max(dp[N], dp[N - 1]);

//    dp[0] = 0;
//    dp[1] = 0;

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

    ans = max(ans, dp[N - 1]);
    dp[0] = dp[1] = dp[2] = dp[3] = 0;
    for (int i = 4; i <= N - 2; ++i) {
        dp[i] = max(dp[i - 1], max(dp[i - 2], a[i] + a[i - 1] + dp[i - 3]));
    }

    g << max(ans, dp[N - 2] + a[1] + a[N]) << '\n';
    return 0;
}