Cod sursa(job #1250858)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 28 octombrie 2014 17:56:18
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>

#include <vector>

int main()
{
  std::ifstream in("oo.in");
  std::ofstream out("oo.out");

  int n;
  in >> n;
  std::vector<int> v(n + 2, 0);
  std::vector<int> oo(n + 2, 0);
  for (int i = 0; i < n; ++i) {
    in >> v[i];
  }
  v[n] = v[0];
  in.close();

  if (n == 2) {
    out << v[0] + v[1] << std::endl;
    out.close();
    return 0;
  }

  if (n == 3) {
    out << v[0] + v[1] + v[2] - std::min(v[0], std::min(v[1], v[2])) <<
        std::endl;
    out.close();
    return 0;
  }

  // Var1. You do NOT pick the first egg.
  oo[0] = 0;
  oo[1] = 0;
  oo[2] = 0;
  oo[3] = v[1] + v[2];
  for (int i = 4; i <= n; ++i) {
    oo[i] = std::max(oo[i - 1], v[i - 1] + v[i - 2] + oo[i - 3]);
  }
  int sol1 = oo[n];

  // Var2. You DO pick the first egg and the second egg.
  oo[0] = 0;
  oo[1] = 0;
  oo[2] = v[0] + v[1];
  for (int i = 3; i < n; ++i) {
    oo[i] = std::max(oo[i - 1], v[i - 1] + v[i - 2] + oo[i - 3]);
  }
  int sol2 = oo[n - 1];

  // Var 3. You DO pick the first egg and the last egg.
  oo[0] = 0;
  oo[1] = v[0] + v[n - 1];
  for (int i = 2; i < n - 1; ++i) {
    oo[i] = std::max(oo[i - 1], v[i - 1] + v[i - 2] + oo[i - 3]);
  }
  int sol3 = oo[n - 2];

  out << std::max(std::max(sol1, sol2), sol3) << std::endl;
  out.close();

  return 0;
}