Cod sursa(job #3227782)

Utilizator CalinHanguCalinHangu CalinHangu Data 2 mai 2024 15:55:05
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>

#define x first
#define y second
#define ll long long
#define pb push_back
#define bg begin()
#define ed end()
#define cl clear()
#define pii pair<int, int>

#define int ll

using namespace std;

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

const int MOD = 1e9 + 7;
const char nl = '\n';
const int NMAX = 1e5 + 5;
const int INF = 1e9;

int n, dp[NMAX], v[NMAX];

int compute(int l, int r){
    dp[l + 1] = v[l] + v[l + 1];
    for(int i = l + 2; i <= r; ++i)
        dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
    int ret = dp[r];
    for(int i = 1; i <= n; ++i)
        dp[i] = 0;
    return ret;
}

signed main()
{
    in >> n;
    for(int i = 1; i <= n; ++i)
        in >> v[i];
    //v[0] = v[n];
    v[n + 1] = v[1];
    int ans = compute(1, n - 1);
    ans = max(ans, compute(2, n));
    ans = max(ans, compute(3, n + 1));
    out << ans << nl;;
    return 0;
}