TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

100.0% (57/57)

Submission's AC Ratio

78.1% (100/128)

Description

    7
   3 8
  8 1 0
 2 7 4 4
4 5 2 6 5
 (圖一)

圖一是一個有數字構成的三角形. 現在請問 從最頂端走到最底端 最大的和是多少。

* 每個點只能往左下或右下走,底層的點不能再往下走。
* 三角形的高度介於1到100之間。
* 三角形上的數字都介於0到99之間。

Input Format

第一個是數字n代表三角形高度。

聰明的你知道接下來是怎樣的格式。

Output Format

輸出一個貌似解答的數字。

Sample Input

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

Sample Output

30

Hints

Problem Source

原TIOJ1288 / 雄中公假社'08 入退社考。(IOI 94 DayI pA)。Problem Setter:ggm。

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6