Cod sursa(job #2070592)

Utilizator cami9719Camelia Hanes cami9719 Data 19 noiembrie 2017 18:26:15
Problema Oo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <bits/stdc++.h>
using namespace std;

vector<int> dp(100003), v(100003);

int main()
{
    ifstream f("oo.in");
    ofstream g("oo.out");
    int n;
    f >> n;
    vector<int> e;
    e.emplace_back(0);
    int c;
    for ( int i = 0; i < n; ++ i ){
        f >> c;
        e.emplace_back(c);
    }
    vector<int> dp(n + 2, 0);
    dp[1] = e[1] + e[n];
    for ( int i = 1; i <= n - 2; ++ i )
        dp[i] = max( dp[i - 1], (i > 3 ? dp[i - 3] : 0) + e[i] + e[i - 1] );
    int max_so_far = dp[n - 2];
    dp[n] = e[n] + e[1];
    for ( int i = n - 1; i > 1; -- i )
        dp[i] = max( dp[i + 1], ( i + 3 < n ? dp[i + 3] : 0) + e[i] + e[i + 1] );
    max_so_far = max( max_so_far, dp[2]);
    g << max_so_far;
    return 0;
}