The Triangle

Time limit: 0.05s Memory limit: 0.5MB Input: the-triangle.in Output: the-triangle.outPoints by default: 10p
        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5      (Figure 1)

Figure 1 shows a number triangle.

Task

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.

Input data

The first line of the input file the-triangle.in will contain an integer nn, the number of rows. The next nn lines will contain space-separated integers, denoting the values of the triangle.

Output data

The first line of the output file the-triangle.out contains the highest sum as required by the problem statement.

Constraints and clarifications

  • 1<n1001 \lt n \le 100
  • The numbers in the triangle, all integers, are between 00 and 9999.

Example

the-triangle.in

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

the-triangle.out

30

Log in or sign up to be able to send submissions!