Bolos Bovinos

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$ ~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$ ~N~ $(1 \le N \le 350)$ ~(1 \le N \le 350)~ filas, determine la suma más grande que se pueda obtener.

Entrada

Línea $1$ ~1~: Un solo entero, $N$ ~N~

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

Salida

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

Ejemplo de Entrada

Ejemplo de Salida

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

0

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

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

0

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é.