// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

struct Partida {
   int   inicio;
   int   final;
   float premio;
   int   primeraPosterior;
};

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 ***************************************************************************/

/*
float maximoPremio(const vector<Partida> & competicion,
                   int partida) {

   // Maximo premio acumulable eligiendo en que partidas participar entre esa partida y la ultima

   float resultado;

   if (partida == competicion.size() - 1)
      resultado = competicion[partida].premio;
   else if (competicion[partida].primeraPosterior == -1)
      resultado = max(competicion[partida].premio,
		      maximoPremio(competicion, partida + 1));
   else
      resultado = max(competicion[partida].premio + maximoPremio(competicion, competicion[partida].primeraPosterior),
		      maximoPremio(competicion, partida + 1));

   return resultado;
  
}

float maximoPremio(const vector<Partida> & competicion) {

   return maximoPremio(competicion, 0);

}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
#define DESCONOCIDO -1

float maximoPremio(const vector<Partida> & competicion,
                   int partida,
                   vector<float> & resultado) {

   if (resultado[partida] == DESCONOCIDO)
      if (partida == competicion.size() - 1)
	 resultado[partida] = competicion[partida].premio;
      else if (competicion[partida].primeraPosterior == -1)
	 resultado[partida] = max(competicion[partida].premio,
				  maximoPremio(competicion, partida + 1, resultado));
      else
	 resultado[partida] = max(competicion[partida].premio + maximoPremio(competicion, competicion[partida].primeraPosterior, resultado),
				  maximoPremio(competicion, partida + 1, resultado));

   return resultado[partida];
  
}

float maximoPremio(const vector<Partida> & competicion) {

   vector<float> resultado(competicion.size(), DESCONOCIDO);
   return maximoPremio(competicion, 0, resultado);

}
*/

/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 ***************************************************************************/

/*
float maximoPremio(const vector<Partida> & competicion) {

   vector<float> resultado(competicion.size());

   for (int partida = competicion.size() - 1; partida >= 0; partida--)
      if (partida == competicion.size() - 1)
	 resultado[partida] = competicion[partida].premio;
      else if (competicion[partida].primeraPosterior == -1)
	 resultado[partida] = max(competicion[partida].premio,
				  resultado[partida + 1]);
      else
	 resultado[partida] = max(competicion[partida].premio + resultado[competicion[partida].primeraPosterior],
				  resultado[partida + 1]);


   return resultado[0];

}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/

int main () {

   vector<Partida> ejemploCompeticion1 = { {10, 14, 7000, 3},
				 	   {11, 12, 3000, 2},
				 	   {13, 17, 9000, 5},
					   {15, 17, 5000, 5},
					   {16, 19, 8000, -1},
					   {17, 18, 2000, -1}
   };

   float resultado;

   resultado = maximoPremio(ejemploCompeticion1);
   cout << "Maximo premio: " << resultado << endl;
   if (resultado == 15000)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

   vector<Partida> ejemploCompeticion2 = { {10, 14, 7000, 3},
				 	   {11, 18, 3000, 7},
				 	   {13, 17, 9000, 5},
					   {15, 17, 5000, 5},
					   {16, 19, 8000, -1},
					   {17, 19, 2000, -1},
					   {17, 18, 4000, 7},
					   {18, 19, 10000, -1},
					   {18, 19, 6000, -1}
   };

   resultado = maximoPremio(ejemploCompeticion2);
   cout << "Maximo premio: " << resultado << endl;
   if (resultado == 26000)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}