Cod sursa(job #2281887)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 12 noiembrie 2018 21:43:43
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ifstream in("oo.in");
    ofstream out("oo.out");

    int n;
    in >> n;
    vector<int> v(n + 1, 0);
    for(int i = 1; i <= n; i ++)
        in >> v[i];

    vector<vector<vector<int>>> dp(n + 1, vector<vector<int>> (2, vector<int> (3, 0)));
    dp[1][1][0] = v[n] + v[1];
    dp[2][1][1] = v[1] + v[2];
    dp[2][0][0] = dp[1][1][0];
    for(int i = 3; i <= n; i ++) {
        for(int j = 0; j < 3; j ++) {
            dp[i][0][j] = max(dp[i - 1][0][j], dp[i - 1][1][j]);
            if(i >= n - 1 && j == 0)
                continue;
            if(i == n && j == 1)
                continue;
            dp[i][1][j] = v[i] + v[i - 1] + dp[i - 2][0][j];
        }

    }
    int ans = 0;
    for(int i = 0; i < 3; i ++)
        ans = max({ans, dp[n][0][i], dp[n][1][i]});
    out << ans;

    return 0;
}