TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的!雖然想像得出來也不一定可以就是了

User's AC Ratio

97.6% (202/207)

Submission's AC Ratio

79.2% (328/414)

Tags

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 1

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

Sample Output 1

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 (VSS, 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