Cod sursa(job #2109850)

Utilizator RaduGiucleaGiuclea Radu RaduGiuclea Data 20 ianuarie 2018 10:47:11
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
using namespace std;
int v[100002],din[4][100002];
int main()
{
    freopen("oo.in","r",stdin);
    freopen("oo.out","w",stdout);
    int n,i,caz1=0,caz2=0,caz3=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
      scanf("%d",&v[i]);
    //nu luam ultimul
    din[1][2]=v[1]+v[2];
    for(i=3;i<=n-1;i++)
      if(v[i]+v[i-1]+din[1][i-3]>din[1][i-1])
        din[1][i]=v[i]+v[i-1]+din[1][i-3];
      else din[1][i]=din[1][i-1];
    caz1=din[1][n-1];
    //luam ultimul+primul
    caz2+=v[1]+v[n];
    din[2][4]=v[3]+v[4];
    for(i=5;i<=n-2;i++)
      if(v[i]+v[i-1]+din[2][i-3]>din[2][i-1])
        din[2][i]=v[i]+v[i-1]+din[2][i-3];
      else din[2][i]=din[2][i-1];
    caz2+=din[2][n-2];
    //luam ultimul+penultimul
    caz3+=v[n-1]+v[n];
    din[3][3]=v[2]+v[3];
    for(i=4;i<=n-3;i++)
      if(v[i]+v[i-1]+din[3][i-3]>din[3][i-1])
        din[3][i]=v[i]+v[i-1]+din[3][i-3];
      else din[3][i]=din[3][i-1];
    caz3+=din[3][n-3];
    if(caz1>=caz2&&caz1>=caz3)
      printf("%d",caz1);
    else if(caz2>=caz1&&caz2>=caz3)
      printf("%d",caz2);
    else if(caz3>=caz1&&caz3>=caz2)
      printf("%d",caz3);
    return 0;
}