Cod sursa(job #3340461)

Utilizator PopRadGabPopescu Radu Gabriel PopRadGab Data 14 februarie 2026 14:28:10
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
using namespace std;

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

#define DIM 1000003
int A[DIM], dp[DIM];

int main(){
    ios::sync_with_stdio(false);
    fin.tie(0);

    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>A[i];

    // caz general de parcurgere
    dp[2]=A[1]+A[2];
    for(int i=2;i<=n;i++)
        dp[i]=max(dp[i-3]+(A[i-1]+A[i]),dp[i-1]); // last + urma sau cel mai bun din urma
        int rasp=dp[n-1];

    // caz in care luam sectoarele n-1 si n
    dp[1]=0; // *
    dp[2]=0; // **       prin * si ** nu permitem alegerea primului sector

    for(int i=3;i<=n;i++)
        dp[i]=max(dp[i-3]+(A[i-1]+A[i]),dp[i-1]);
    rasp=max(rasp,dp[n]);

    // caz in carea luam n si 1
    dp[1]=0; // *
    dp[2]=0; // **   prin * , ** si *** nu permitem alegerea sectoarelor 1 si 2 pentru a nu distruge n
    dp[3]=0; // ***

    for(int i=4;i<=n;i++)
        dp[i]=max(dp[i-3]+(A[i-1]+A[i]),dp[i-1]);
    rasp=max(rasp,dp[n-2]+(A[n]+A[1]));

    fout<<rasp;
    return 0;
}