Cod sursa(job #2418242)

Utilizator SemetgTemes George Semetg Data 4 mai 2019 14:38:04
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

const string FILE_NAME = "oo";
const int N_MAX { 100005 };
using Node = pair< int, pair<int, int> >;

ifstream in { FILE_NAME + ".in" };
ofstream out { FILE_NAME + ".out" };

int N;
vector<char> a(N_MAX);
vector<int> dp(N_MAX);
int sol;

void init() {
    in >> N;
    
    for (int i { 1 }; i <= N; ++i) {
        int x;
        in >> x;
        a[i] = x;
    }
}

void DP(int NMax) {
    for (int i { 4 }; i <= NMax; ++i)
        dp[i] = max(dp[i - 1], a[i] + a[i - 1] + dp[i - 3]);
}

void solve() {
    // 1 si 2
    dp[1] = 0;
    dp[2] = a[1] + a[2];
    dp[3] = dp[2];
    DP(N - 1);
    sol = dp[N - 1];
    
    // 2 si 3
    dp[1] = dp[2] = 0;
    dp[3] = a[2] + a[3];
    DP(N);
    sol = max(sol, dp[N]);
    
    // 1 si N
    dp[1] = a[1] + a[N];
    dp[2] = dp[3] = dp[1];
    DP(N - 2);
    sol = max(sol, dp[N - 2]);
}

void print() {
    out << sol;
}

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