TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

67.7% (21/31)

Submission's AC Ratio

22.6% (31/137)

Tags

Description

  在第501統合戦闘航空団裡,你是一個傳令兵隊的隊長(在傳訊系統的最上層),你要負責將只令下達下去,你們的團隊有種非常特別的傳訊方式(如圖上的方式)。

  圖上的數字則代表回到崗位的時間,而箭頭則代表傳訊的方向。

  而傳令的條件如下:

   1.傳令時必須兩個人都在工作崗位上

   2.傳令需要花費一單位的時間

  現在你知道有 $\frac{n(n+1)}{2}$ 個人( $n$ 層傳輸層),以及每個人回到崗位的時間,最快要讓所有人知道訊息需要多久?

Input Format

本題有多筆測試資料,以 EOF 為結束

每筆測試資料的:

第一行有一個數字 $n$,代表有 $n$ 個傳輸層($1 \le n \le 100$)

第二行開始有 $n$ 行,第 $i$ 行共有 $i$ 個數字以空白隔開,代表該人回到崗位的時間 $T$($1 \le T \le 100$)

Output Format

對每筆資料輸出一個數字 $k$,代表最少要花 $k$ 單位的時間才能讓所有人知道訊息

Sample Input 1

3
1
9 9
1 2 3

Sample Output 1

11

Hints

Problem Source

原TIOJ1391 / 快樂暑假營第三次練習比賽。
Problem Setter:hallogameboy
2024/02/27 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2