Cod sursa(job #2121517)

Utilizator preda.andreiPreda Andrei preda.andrei Data 3 februarie 2018 19:51:36
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.86 kb
#include <fstream>
#include <vector>

using namespace std;

int FindBest(const vector<int> &eggs, int start, int len)
{
  vector<int> best(eggs.size(), 0);
  for (int i = 1; i < len; ++i) {
    auto pos = start + i;

    best[pos] = eggs[pos] + eggs[pos - 1];
    if (i > 2) {
      best[pos] += best[pos - 3];
    }

    best[pos] = max(best[pos], best[pos - 1]);
  }
  return best[start + len - 1];
}

int main()
{
  ifstream fin("oo.in");
  ofstream fout("oo.out");

  int chickens;
  fin >> chickens;

  vector<int> eggs(chickens + 5);
  for (int i = 0; i < chickens; ++i) {
    int num;
    fin >> num;
    eggs[i] = num;
  }

  auto res = FindBest(eggs, 0, chickens - 1);
  for (int i = chickens; i < (int)eggs.size(); ++i) {
    eggs[i] = eggs[i - chickens];
    res = max(res, FindBest(eggs, i - chickens + 1, chickens - 1));
  }

  fout << res << "\n";
  return 0;
}