IOI '94 P1 - The Triangle

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.6s
Memory limit: 16M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
            7
          3   8
        8   1   0
      2   7   4   4
    4   5   2   6   5     (Figure 1)

Figure 1 shows a number triangle.

Write a program that calculates the highest sum of numbers passed on a route that starts at the top and ends somewhere on the base.

  • Each step can go either diagonally down to the left or diagonally down to the right.
  • The number of rows in the triangle is > 1 but \le 100.
  • The numbers in the triangle, all integers, are between 0 and 99.

Input Specification

The first line of input will contain an integer N. The i^{th} of the next N lines will contain i space-separated integers, denoting the values of the triangle.

Output Specification

The highest sum as required by the problem statement.

Sample Input

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

Sample Output

30

Comments

There are no comments at the moment.