Cod sursa(job #2152259)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 5 martie 2018 13:15:38
Problema Oo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("oo.in");
ofstream fout("oo.out");

const int nMax = 100001;
int n;
int a[nMax], dp[nMax];

void Read() {
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    fin.close();
}

void Solve() {
    int i;
    /// Cazul 1. Iau primele 2 gaian
    dp[1] = a[1];
    dp[2] = a[1] + a[2];
    for (i = 3; i < n; i++)
        dp[i] = max(a[i - 1] + a[i] + dp[i - 3], dp[i - 1]);
    int ans = dp[n - 1];
    /// Cazul 2. Nu iau prima gaina
    dp[1] = 0;
    dp[2] = a[2];
    dp[3] = a[2] + a[3];
    for (i = 4; i <= n; i++) {
        dp[i] = max(a[i - 1] + a[i] + dp[i - 3], dp[i - 1]);
    }
    ans = max(ans, dp[n]);
    /// Cazul 3. nu iau primele2 gaini
    dp[1] = 0;
    dp[2] = 0;
    dp[3] = a[3];
    dp[4] = a[3] + a[4];
    for (i = 5; i <= n; i++) {
        dp[i] = max(a[i - 1] + a[i] + dp[i - 3], dp[i - 1]);
    }
    ans = max(ans, dp[n]);
    fout << ans << "\n";
}

int main() {
    Read();
    Solve();
    return 0;
}