// Descomenta la version que quieras probar

#include <iostream>
#include <vector>

using namespace std;

/***************************************************************************
 VERSION 1: RECURSIVA, INEFICIENTE
 Esta version no se pide en el examen
 ***************************************************************************/

/*
float maximoBeneficio(const vector<vector<float> > & beneficio,
		      int jugadores,
		      int equipo) {

   // Maximo beneficio que se puede obtener repartiendo esa cantidad de jugadores
   // entre los equipos 0 a equipo ambos inclusive

   float resultado;

   if (equipo == 0)
      resultado = beneficio[jugadores][equipo];
   else {
      resultado = 0;
      for (int asignados = 0; asignados <= jugadores; asignados++)
	 resultado = max(resultado,
			 beneficio[asignados][equipo] + maximoBeneficio(beneficio, jugadores - asignados, equipo - 1));
   }
   return resultado;
}

float maximoBeneficio(const vector<vector<float> > & beneficio) {

   return maximoBeneficio(beneficio, beneficio.size() - 1, beneficio[0].size() - 1);

}
*/

/***************************************************************************
 VERSION 2: RECURSIVA, EFICIENTE
 Coste temporal: O(n^2 * q)
 Coste espacial: O(n * q)
***************************************************************************/

/*
#define DESCONOCIDO -1

float maximoBeneficio(const vector<vector<float> > & beneficio,
		      vector<vector<float> > & resultado,
		      int jugadores,
		      int equipo) {


   if (resultado[jugadores][equipo] == DESCONOCIDO)

      if (equipo == 0)
	 resultado[jugadores][equipo] = beneficio[jugadores][equipo];
      else {
	 resultado[jugadores][equipo] = 0;
	 for (int asignados = 0; asignados <= jugadores; asignados++)
	    resultado[jugadores][equipo] = max(resultado[jugadores][equipo],
					       beneficio[asignados][equipo] + maximoBeneficio(beneficio, resultado, jugadores - asignados, equipo - 1));
      }

   return resultado[jugadores][equipo];

}

float maximoBeneficio(const vector<vector<float> > & beneficio) {

   vector<vector<float> > resultado(beneficio.size(), vector<float>(beneficio[0].size(), DESCONOCIDO));

   return maximoBeneficio(beneficio, resultado, beneficio.size() - 1, beneficio[0].size() - 1);

}
*/


/***************************************************************************
 VERSION 3: NO RECURSIVA, EFICIENTE
 Coste temporal: O(n^2 * q)
 Coste espacial: O(n * q)
 ***************************************************************************/

/*
float maximoBeneficio(const vector<vector<float> > & beneficio) {

   vector<vector<float> > resultado(beneficio.size(), vector<float>(beneficio[0].size()));

   for (int equipo = 0; equipo < beneficio[0].size(); equipo++)
      for (int jugadores = 0; jugadores < beneficio.size(); jugadores++)
	 if (equipo == 0)
	    resultado[jugadores][equipo] = beneficio[jugadores][equipo];
	 else {
	    resultado[jugadores][equipo] = 0;
	    for (int asignados = 0; asignados <= jugadores; asignados++)
	       resultado[jugadores][equipo] = max(resultado[jugadores][equipo],
						  beneficio[asignados][equipo] + resultado[jugadores - asignados][equipo - 1]);
	 }

   return resultado[beneficio.size() - 1][beneficio[0].size() - 1];

}
*/

/***************************************************************************
 EJEMPLO
 ***************************************************************************/
	 
int main () {
   vector<vector<float> > ejemploBeneficio = { { 0,  0,  0},
					       {30, 10, 20},
					       {50, 60, 20},
					       {60, 70, 40},
					       {65, 80, 80},
					       {65, 85, 100} };

   if (maximoBeneficio(ejemploBeneficio) == 130)
      cout << "OK" << endl;
   else
      cout << "MAL" << endl;

}