Cod sursa(job #2823994)

Utilizator lolismekAlex Jerpelea lolismek Data 30 decembrie 2021 15:04:58
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <iostream>
#include <fstream>

#define int long long

using namespace std;

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

const int N = 1e5;
int dp[N + 1], v[N + 1], ans;

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

void solve(int n){
    /*
    Consideram urmatoarele trei cazuri:
        > luam primele doua gaini => iteram pana la n - 1
        > luam prima si ultima => iteram pana la n - 2
        > nu ne atingem de prima => iteram pana la n
    */

    // primul caz:
    dp[1] = v[1];
    dp[2] = dp[1] + v[2];
    for(int i = 3; i <= n - 1; i++)
        dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
    ans = max(ans, dp[n - 1]);
    // al doilea caz:
    clear_dp(n);
    dp[1] = v[1] + v[n];
    for(int i = 2; i <= n - 2; i++)
        dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
    ans = max(ans, dp[n - 2]);
    // al treilea caz:
    clear_dp(n);
    dp[2] = v[2];
    dp[3] = v[2] + v[3];
    for(int i = 4; i <= n; i++)
        dp[i] = max(dp[i - 1], dp[i - 3] + v[i] + v[i - 1]);
    ans = max(ans, dp[n]);
}

signed main(){
    int n;
    fin >> n;
    for(int i = 1; i <= n; i++) fin >> v[i];
    
    solve(n);
    fout << ans;
    return 0;
}