Suma máxima en un camino descendente
Dada una cuadrícula de altura
h y de ancho w, se te pide calcular la suma máxima que puede obtenerse al desplazarse desde la parte superior hasta la parte inferior. En cada paso, solo se permite moverse a las 3 celdas adyacentes que están justo abajo. En otras palabras, si te encuentras en la posición (r, c), puedes pasar a (r + 1, c - 1), (r + 1, c), o (r + 1, c + 1). Por eso lo llamamos una suma al caer: descendemos desde la parte superior de la cuadrícula hasta el fondo. Encuentra la máxima suma posible en el recorrido.ㅤ | o | ㅤ | ㅤ |
↙️ | ⬇️ | ↘️ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
ㅤ | ㅤ | ㅤ | ㅤ |
Entrada
La primera línea de la entrada contiene dos números enteros
h y w (1 ≤ h, w ≤ 100).Las siguientes
h líneas contienen w números (-100 ≤ ≤ 100), que representan los valores de la cuadrícula en la fila r y la columna c.Salida
El programa debe imprimir la suma máxima que se pueda obtener entre todas las posibles rutas de caída.
Examples
Entrada | Salida |
3 3
2 1 3
6 5 4
7 8 9 | 17 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB