Time limit 4000/7000/7000/7000 ms. Memory limit 65000/65000/65000/65000 Kb.
Olympiad 2012. Prepared by: Evis Hoxha.
Difficulty Beta
Question 4. Triangle
Shqip
Given a triangle like the one below:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
Write a program that calculates the maximum sum of the numbers that can be obtained by following a way that starts in the vertex of the triangle and ends in a point in the base.
Each step proceeds diagonal down: left or right.
Input
In the first line is given a number n, the number of the lines of the triangle, where 1<n<=100.
Then in the following n lines the values of the triangle are given. Each value is between 0 and 9.
Output
Show the maximal sum.
|
Input I
|
| 5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5 |
| Output 1 |
30 |
Для отправки решений необходимо выполнить вход.
|