Bolos Bovinos


Submit solution

Points: 100
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Pascal, Perl, Prolog, Python, Scala, Swift, VB

Las vacas no usan las bolas usuales de bolos cuando van a jugar bolos. A pesar de eso, cada una toma un número (en el rango 1..99), y se alinean en un triángulo estándar de bolos como esto:

          7

        3   8

      8   1   0

    2   7   4   4

  4   5   2   6   5

Entonces las otras vacas recorren el triángulo comenzando desde su parte superior y se mueven "abajo" hacia una de las dos vacas adyacentes en diagonal hasta que se llega a la fila "de abajo". Las vacas obtienen como puntaje la suma de los números de las vacas visitadas en el camino. La vaca con el más alto puntaje gana esa línea. Dado un triángulo con N (1 \le N \le 350) filas, determine la suma más grande que se pueda obtener.

Entrada

Línea 1: Un solo entero, N

Líneas 2..N+1: La línea i+1 contiene i enteros separados por espacios que representan la fila i del triángulo.

Salida

Línea 1: La suma más grande que se puede obtener usando las reglas de recorrido.

Ejemplo de Entrada

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

Ejemplo de Salida

30

Detalles de la Salida

          7
         *
        3   8
       *
      8   1   0
       *
    2   7   4   4
       *
  4   5   2   6   5

La suma más grande se puede obtener recorriendo las vacas como se muestra antes.


Comments


  • -1
    Bryanm  commented on Nov. 7, 2019, 2:49 a.m.

    pipo eso fue lo que hice pero me rte no se que pasa


  • -1
    Bryanm  commented on Nov. 6, 2019, 8:16 p.m.

    el caso # 8 me RTE y todos los demas me dan bien alguien puede decirme que tengo mal


    • 6
      Primervirgen  commented on Nov. 7, 2019, 2:12 a.m.

      Papo eso es una DP clásica tipo coeficientes binomiales, llevas en cada casilla del array la mejor suma del anterior de arriba y él de la derecha, y luego t quedas con la mayor suma


      • 5
        linkyless  commented on Aug. 30, 2022, 1:46 a.m.

        Es lo mejor del ejercicio, uno de los primeros problemas de DP que estudié.