Cod sursa(job #2072301)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 21 noiembrie 2017 18:13:41
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <fstream>

using namespace std;

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

int max_5_numere(int a, int b, int c, int d, int e){
  int maxim;

  maxim = max(a, b);
  maxim = max(maxim, c);
  maxim = max(maxim, d);
  maxim = max(maxim, e);

  return maxim;
}

int n, v[100001];
int dp[100001];
int max1, max2, max3;

int main(){
  in >> n;

  for (int i = 1; i <= n; ++ i)
    in >> v[i];

  v[0] = v[n];

  if (n == 2){
    out << v[1] + v[2];
  }
  if (n == 3){
    out << max_5_numere(v[1] + v[2], v[2] + v[3], v[3] + v[1], 0, 0);
  }
  if (n == 4){
    out << max_5_numere(v[1] + v[2], v[2] + v[3], v[3] + v[4], v[4] + v[1], 0);
  }
  if (n == 5){
    out << max_5_numere(v[1] + v[2], v[2] + v[3], v[3] + v[4], v[4] + v[5], v[5] + v[1]);
  }
  if (n >= 6){
    dp[1] = v[0] + v[1];
    dp[2] = max_5_numere(v[0] + v[1], v[1] + v[2], 0, 0, 0);
    dp[3] = max_5_numere(v[0] + v[1], v[1] + v[2], v[2] + v[3], 0, 0);
    dp[4] = max_5_numere(0, dp[4 - 2], dp[4 - 3] + v[4] + v[4 - 1], 0, 0);
    dp[5] = max_5_numere(0, dp[5 - 2], dp[5 - 3] + v[5] + v[5 - 1], dp[5 - 4] + v[5] + v[5 - 1], 0);

    //out << dp[1]<< " " << dp[2] << " " << dp[3] << " " << dp[4] << " " << dp[5] << " ";

    for (int i = 6; i <= n - 2; ++ i){
      dp[i] = max_5_numere(0, dp[i - 2], dp[i - 3] + v[i] + v[i - 1], dp[i - 4] + v[i] + v[i - 1], dp[i - 5] + v[i] + v[i - 1]);
      //out << dp[i] << " ";
    }
    //out << '\n';
    max1 = max_5_numere(dp[n - 2], dp[n - 3], dp[n - 4], dp[n - 5], dp[n - 6]);
    for (int i = 1; i <= n; ++ i)
      dp[i] = 0;




    dp[2] = v[1] + v[2];
    dp[3] = max_5_numere(v[1] + v[2], v[2] + v[3], 0, 0, 0);
    dp[4] = max_5_numere(v[1] + v[2], v[2] + v[3], v[3] + v[4], 0, 0);
    dp[5] = max_5_numere(0, dp[5 - 2], dp[5 - 3] + v[5] + v[5 - 1], 0, 0);
    dp[6] = max_5_numere(0, dp[6 - 2], dp[6 - 3] + v[6] + v[6 - 1], dp[6 - 4] + v[6] + v[6 - 1], 0);

    //out << dp[2]<< " " << dp[3] << " " << dp[4] << " " << dp[5] << " " << dp[6] << " ";

    for (int i = 7; i <= n - 1; ++ i){
      dp[i] = max_5_numere(0, dp[i - 2], dp[i - 3] + v[i] + v[i - 1], dp[i - 4] + v[i] + v[i - 1], dp[i - 5] + v[i] + v[i - 1]);
      //out << dp[i] << " ";
    }
    //out << '\n';
    max2 = max_5_numere(dp[n - 1], dp[n - 2], dp[n - 3], dp[n - 4], dp[n - 5]);
    for (int i = 1; i <= n - 1; ++ i)
      dp[i] = 0;




    dp[3] = v[2] + v[3];
    dp[4] = max_5_numere(v[2] + v[3], v[3] + v[4], 0, 0, 0);
    dp[5] = max_5_numere(v[2] + v[3], v[3] + v[4], v[4] + v[5], 0, 0);
    dp[6] = max_5_numere(0, dp[6 - 2], dp[6 - 3] + v[6] + v[6 - 1], 0, 0);
    dp[7] = max_5_numere(0, dp[7 - 2], dp[7 - 3] + v[7] + v[7 - 1], dp[7 - 4] + v[7] + v[7 - 1], 0);

    //out << dp[3]<< " " << dp[4] << " " << dp[5] << " " << dp[6] << " " << dp[7] << " ";

    for (int i = 8; i <= n; ++ i){
      dp[i] = max_5_numere(0, dp[i - 2], dp[i - 3] + v[i] + v[i - 1], dp[i - 4] + v[i] + v[i - 1], dp[i - 5] + v[i] + v[i - 1]);
      //out << dp[i] << " ";
    }
    //out << '\n';
    max3 = max_5_numere(dp[n], dp[n - 1], dp[n - 2], dp[n - 3], dp[n - 4]);




    //out << max1 << " " << max2 << " " << max3 << " " << '\n';
    out << max_5_numere(max1, max2, max3, 0, 0);

  }

  return 0;
}