HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50680 - Triangle

Guest
• Discussion of problem (1)

Section problems

• 50930 - Tom and Jerry
• 50526 - Gold Market
• 50488 - Connecting Wires
• 50681 - Center of a Series
• 50561 - Lucky tickets
• 50598 - Minimum Sum
• 50601 - Increasing sequence
• 50613 - Zapakovka
• 50680 - Triangle
• 50683 - Parking Buses
• 50685 - Guest Room Usage
• 50544 - Stock market
• 50545 - Diet

Feedback

If you notice incorrect translations in Contester, please let author know.

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


Для отправки решений необходимо выполнить вход.

www.contester.ru