Cod sursa(job #2239137)

Utilizator Cojocaru_Andrei_CristianCojocaru Andrei Cristian Cojocaru_Andrei_Cristian Data 9 septembrie 2018 15:50:14
Problema Oo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <algorithm>
using namespace std;
int dp1[100005][5],dp2[100005][5],dp3[100005][5],v[100005];
int main()
{   ifstream cin("oo.in");
    ofstream cout("oo.out");
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    for(int i=1;i<=n-2;i++)
    {
        if(i!=1&&i!=2)
       {
           dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]);
           dp1[i][1]=v[i]+v[i-1]+dp1[i-2][0];
       }
      else
      {
          if(i==1)
          {
              dp1[i][0]=0;
              dp1[i][1]=v[i];
          }
          else
          {
              dp1[i][0]=max(dp1[i-1][0],dp1[i-1][1]);
              dp1[i][1]=v[i]+v[i-1];
          }
      }
    }
    for(int i=2;i<=n;i++)
    {   if(i!=2){
        dp2[i][0]=max(dp2[i-1][0],dp2[i-1][1]);
        dp2[i][1]=v[i]+v[i-1]+dp2[i-2][0];}
        else
        {
            dp2[i][0]=0;
            dp2[i][1]=v[i];
        }
    }
    dp3[n][0]=0;
    dp3[n][1]=v[n];
    dp3[1][0]=v[n];
    dp3[1][1]=v[1]+v[n];
    for(int i=2;i<=n-2;i++)
    {
        dp3[i][0]=max(dp3[i-1][0],dp3[i-1][1]);
        dp3[i][1]=v[i]+v[i-1]+dp3[i-2][0];

    }
    cout<<max(dp2[n][1],max(dp2[n][0],max(dp1[n-2][1],max(dp1[n-2][0],max(dp3[n-2][0],dp3[n-2][1])))));
    return 0;
}