Cod sursa(job #3281929)

Utilizator ALEXANDRUspargoaseAlexandru Joita ALEXANDRUspargoase Data 4 martie 2025 09:03:48
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.12 kb
// dinamica circulara
/// (i, i+1) -> i - 1 & i + 2
/// (1, 2) -> n & 3
/// => (n-1, n) -> n - 2 & 1
/// Se observa ciclu in graful depenentelor

/*
dp[i] = max(dp[i-1], dp[i-3]) + (a[i] + a[i-1])
*/

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

// solve calculează numărul maxim de ouă pe care le poate aduna fermierul într-un interval liniar
//  [1, n], [2, n + 1], [3, n + 2]

int v[100005];
int n, add;
int dp[100006];
int solve(int start, int end)
{
    for (int i = 1; i <= n + 1; i++)
        dp[i] = 0;

    for (int i = start + 1; i <= end + start + 1; i++)
    {
        add = 0;
        if (i >= 4)
        {
            add = dp[i - 3];
        }
        dp[i] = std::max(dp[i - 1], v[i] + v[i - 1] + add);
    }
    return dp[start + n - 2];
}

int main()
{

    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> v[i];
    }
    v[n + 1] = v[1];
    int rez = std::max(solve(1, n), std::max(solve(2, n), solve(3, n)));
    fout << rez;
    return 0;
}