// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

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

/*
float maxPuntos(const vector<vector<float> > & puntos,
		int reto,
		int dia) {

   // Maxima cantidad de puntos que se pueden acumular desde el dia 0 hasta ese dia
   // si ese dia se supera ese reto
   
   float resultado;

   if (dia == 0)
      resultado = 0;
   else {
      float maximo = 0;
      for (int retoPrevio = 0; retoPrevio < puntos.size(); retoPrevio++)
	 maximo = max(maximo,
		      maxPuntos(puntos, retoPrevio, dia - 1) + puntos[retoPrevio][reto]);
      resultado = maximo;
   }

   return resultado;

}

float maxPuntos(const vector<vector<float> > & puntos,
		int dias) {

   float maximo = 0;
   for (int retoFinal = 0; retoFinal < puntos.size(); retoFinal++)
      maximo = max(maximo,
		   maxPuntos(puntos, retoFinal, dias - 1));

   return maximo;

}
*/


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

/*
#define DESCONOCIDO -1

float maxPuntos(const vector<vector<float> > & puntos,
		int reto,
		int dia,
		vector<vector<float> > & resultado) {
   
   if (resultado[reto][dia] == DESCONOCIDO)
      if (dia == 0)
	 resultado[reto][dia] = 0;
      else {
	 float maximo = 0;
	 for (int retoPrevio = 0; retoPrevio < puntos.size(); retoPrevio++)
	    maximo = max(maximo,
			 maxPuntos(puntos, retoPrevio, dia - 1, resultado) + puntos[retoPrevio][reto]);
	 resultado[reto][dia] = maximo;
      }

   return resultado[reto][dia];

}

float maxPuntos(const vector<vector<float> > & puntos,
		int dias) {

   vector<vector<float> > resultado(puntos.size(), vector<float>(dias, DESCONOCIDO));
   
   float maximo = 0;
   for (int retoFinal = 0; retoFinal < puntos.size(); retoFinal++)
      maximo = max(maximo,
		   maxPuntos(puntos, retoFinal, dias - 1, resultado));

   return maximo;

}
*/

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

/*
float maxPuntos(const vector<vector<float> > & puntos,
		int dias) {

   vector<vector<float> > resultado(puntos.size(), vector<float>(dias));

   for (int dia = 0; dia < dias; dia++)
      for (int reto = 0; reto < puntos.size(); reto++)
	 if (dia == 0)
	    resultado[reto][dia] = 0;
	 else {
	    float maximo = 0;
	    for (int retoPrevio = 0; retoPrevio < puntos.size(); retoPrevio++)
	       maximo = max(maximo,
			    resultado[retoPrevio][dia - 1] + puntos[retoPrevio][reto]);
	    resultado[reto][dia] = maximo;
	 }

   float maximo = 0;
   for (int retoFinal = 0; retoFinal < puntos.size(); retoFinal++)
      maximo = max(maximo,
		   resultado[retoFinal][dias - 1]);

   return maximo;

}
*/

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

int main () {

   vector<vector<float> > puntos = { {  60,  70, 120, 610,  50},
				     { 210, 300, 170, 600, 100},
				     { 150, 450, 100, 500,  40},
				     { 110,   0,  30,  10,  20},
				     { 620, 320,  90, 240,  80} };

   float resultado = maxPuntos(puntos, 4);
   cout << "Maxima cantidad de puntos: " << resultado << endl;
   if (resultado == 1350)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;
}