Cod sursa(job #1250870)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 28 octombrie 2014 18:08:20
Problema Oo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 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);
  std::string s;
  getline(in, s);
  getline(in, s);
  int ssize = s.size();
  for (int i = 0; i < s.size(); ++i) {
    if (s[i] < '0' || s[i] > '9') {
      s[i] = 0;
    }
  }
  int next = 0;
  for (int i = 0; i < ssize; ++i) {
    if (s[i] != 0 && (i == 0 || s[i - 1] == 0)) {
      sscanf(&s[i], "%d", &v[next]);
      next++;
    }
  }
  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;
}