Cod sursa(job #3121691)

Utilizator stefdascalescuStefan Dascalescu stefdascalescu Data 14 aprilie 2023 20:00:31
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <bits/stdc++.h>
#define N 100000
using namespace std;
int v[N + 2], dp[N + 2];
// dp[i] => suma maxima daca luam in considerare toate elementele pana la i
 
int compute(int start, int n)
{
    for(int i = 1; i <= n + 1; i++)
        dp[i] = 0;
    for(int i = start + 1; i < start + n - 1; i++)
    {
        dp[i] = max(dp[i - 1], dp[i - 3 > 0 ? (i - 3) : 0] + v[i - 1] + v[i]);
        /// I -> nu il luam pe i
        /// II -> il luam pe i, dar i este al doilea element
    }
    return dp[start + n - 2];
}
 
int main() {
    int n, i;
    freopen("oo.in" ,"r", stdin);
    freopen("oo.out" ,"w", stdout);
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", &v[i]);
    v[n + 1] = v[1];
    cout << max(compute(3, n), max(compute(1, n), compute(2, n)));
 
    return 0;
}