Cod sursa(job #2729155)

Utilizator vladstefanVlad Oros vladstefan Data 24 martie 2021 12:45:55
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.8 kb

// problema oo

#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>

#define NMax 100000

using namespace std;

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

int n, o[NMax + 3], dp[4][NMax + 3];

void input() {
    fin >> n;
    for (int i = 1; i <= n; ++i) fin >> o[i];
}

void init() {
    dp[0][2] = o[1] + o[2];
    dp[1][3] = o[2] + o[3];
    dp[2][4] = o[3] + o[4];
    for (int k = 0; k <= 2; ++k)
        for (int i = k + 3; i <= n - (k == 0); ++i)
            dp[k][i] = max(dp[k][i - 1], (dp[k][i - 3] + o[i] + o[i - 1]));
}

void solve() {
    fout << max(dp[0][n - 1], max(dp[1][n], dp[2][n - 2] + o[1] + o[n]));
}

int main() {
    input();
    init();
    solve();
}