Cod sursa(job #3178178)

Utilizator Ruxandra009Ruxandra Vasilescu Ruxandra009 Data 1 decembrie 2023 12:46:12
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <fstream>
#include <climits>

using namespace std;

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

const int nmax = 100005;
int n, a[nmax], dp[nmax], maxi;

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

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

    /// luam 1 si n
    dp[1] = dp[2] = dp[3] = a[1] + a[n];
    for(int i = 4; i <= n - 2; i ++)
        dp[i] = max(a[i] + a[i - 1] + dp[i - 3], dp[i - 1]);

    maxi = max(maxi, dp[n - 2]);
    clean();

    /// luam 1 si 2
    dp[1] = dp[2] = dp[3] = dp[4] = a[1] + a[2];
    for(int i = 5; i <= n - 1; i ++)
        dp[i] = max(a[i] + a[i - 1] + dp[i - 3], dp[i - 1]);

    maxi = max(maxi, dp[n - 1]);
    clean();

    /// nu luam 1
    for(int i = 3; i <= n; i ++)
        dp[i] = max(a[i] + a[i - 1] + dp[i - 3], dp[i - 1]);


    g << max(maxi, dp[n]);
    return 0;
}