Cod sursa(job #2152067)

Utilizator radiogard1999Dragoi Andrei radiogard1999 Data 5 martie 2018 10:41:05
Problema Oo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <bits/stdc++.h>
#define Nmax 100003
using namespace std;
ifstream fin("oo.in");
ofstream fout("oo.out");
int v[Nmax],dp[Nmax][2],n;
///dp[i][0,1]=suma max pe care o pot obtine pana la poz i
///           0-fara sa aleg ultimul el i
///           1-aleg ultimul elem i
void Citire()
{
    int i;
    fin>>n;
    for(i=1;i<=n;i++)
        fin>>v[i];
    fin.close();
}
void Rezolvare()
{
    int i,sol;
    ///init(circular)
    v[0]=v[n];
    dp[1][1]=v[0]+v[1];
    ///
    for(i=1;i<n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
    }
    sol=max(dp[n-1][0],dp[n-1][1]);
    ///init(circular)
    for(i=1;i<=n;i++) dp[i][0]=dp[i][1]=0;
    dp[2][1]=v[1]+v[2];
    for(i=3;i<n;i++)
    {
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        dp[i][1]=dp[i-2][0]+v[i]+v[i-1];
    }
    sol=max(sol,max(dp[n][1],dp[n][0]));
    fout<<sol<<"\n";
    fout.close();
}
int main()
{
    Citire();
    Rezolvare();
    return 0;
}