El monstruo y el gato.


Submit solution

Points: 45 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C++, Java, JS, Pascal, Python, VB

El gato de uno de los azucareros del centro quiere escapar de su enemigo mortal: el monstruso Urón. Actualmente está atrapado en una mesa cuadrada (tablero en lo adelante) de NxM llena de comida colocada por Urón para retrasar la fuga del gato. Las filas del tablero están numeradas con los números del 1 al N, las columnas están numeradas con los números del 1 al M y el gato se ubica inicialmente en la celda (S_X,S_Y). La comida colocada en la celda (i,j) tiene placer a_{i,j} para el gato, y es posible que algunos alimentos traigan placer negativo. Cuando el gato está en una celda, siempre come la comida que hay en ella.

Dado que el monstruo parte de una posición al noroeste del gato, el gato se mueve en dirección sureste. Esto significa que si actualmente está en la celda (X,Y), puede saltar de la mesa para escapar de la trampa o saltar a una de las celdas al sureste de (X,Y). Específicamente, puede saltar a celdas con números (a,b) \neq (X,Y) para las cuales X \le a \le N y Y \le b \le M. El gato intentará escapar de la mesa habiendo maximizado el placer experimentado.

Por lo tanto, escriba un programa que, para cada posible celda inicial (S_X,S_Y), encuentre el máximo placer que el gato puede experimentar mientras huye del monstruo y se mueve de acuerdo con las reglas descritas. Para poner a prueba tus habilidades (y no mirar un montón de números), el gato sólo te pide la suma de estos números.

Entrada

Los números naturales N y M se ingresan desde la primera línea de la entrada estándar: el número de filas y columnas del tablero. De cada una de las siguientes N filas, aparecen M enteros que son los placeres de la comida a la fila correspondiente.

Salida

Genera un solo número: la suma máxima de los placeres antes del escape del gato para cada posible celda inicial (S_X,S_Y).

Restricciones

  • 1 \le N,M \le 500
  • -1000 \le a_{i,j} \le 1000

Ejemplo de Entrada

4 3 
1 2 3 
-2 -3 0 
-1 4 -2 
3 -1 -1

Ejemplo de Salida

25

La siguiente tabla muestra los placeres máximos si el gato parte de cada celda:

7 6 3 
2 1 0 
3 4 -2 
3 -1 -1

Para lograr el máximo placer, comenzando desde la celda (2,1), el camino del gato debe ser: (2,1) -> (3,2), luego salta de la mesa y de la trampa. El placer acumulado será (-2) + 4 = 2.


Comments

There are no comments at the moment.