TopCoder

User's AC Ratio

98.4% (62/63)

Submission's AC Ratio

62.4% (148/237)

Description

  一個數字棋盤遊戲,一開始可在棋盤中任選一格為起點,並規定下一步只能選擇起點的右方或下方格子;選擇其中一個方向後,同樣只能自該選擇的格子選擇往右方或是下方的格子推進,依此類推繼續走下去,不能再回頭。每一個格子都有分數,選擇該格子就能取得上面的分數,但是分數有正得分也有負得分(扣分)。玩家可在任意時候決定不再繼續走,或是依規則走完所有能走的格子。以底下3 x 4的棋盤為例,若選擇以第 2 列第1行為起點,依序通過 3 → -1 → 8 → 6,可得此棋盤最高可得分數 16。

-8 0 4 -4
3 -1 -9 3
-2 8 6 -1

  給定棋盤上每一格的分數,請寫一個程式來找出最高可得分數。

Input Format

第一列是兩個整數 m, n,代表棋盤維度大小(m 列 n 行),3 ≤ m, n ≤ 3,000(棋盤實際大小請參照評分說明)。接下來是依照棋盤維度,共有 m 列,每一列有n個整數,代表每一格的得分score,-9 ≤ score ≤ 9,且至少有一個 score > 0。

Output Format

輸出一個整數,該整數為你的程式所找的最大得分。

Sample Input

#輸入範例1
3 3
3 2 5
9 -2 6
4 -8 3

#輸入範例2
3 5
5 -8 5 2 4
1 1 -9 1 -2
2 -9 3 -3 9

Sample Output

#輸出範例1
19

#輸出範例2
18

Hints

輸入範例1的走法為3→2→5→6→3或3→9→-2→6→3;
輸入範例2的走法為5→2→4→-2→9

本題共有五組測試資料。
第一組測試資料3 ≤ m, n ≤ 5,0 ≤ score ≤ 9 ,共20 分;
第二組測試資料3 ≤ m, n ≤ 5,-9 ≤ score ≤ 9 ,共20 分;
第三組測試資料3 ≤ m, n ≤ 100,0 ≤ score ≤ 9 ,共20 分;
第四組測試資料3 ≤ m, n ≤ 100,-9 ≤ score ≤ 9 ,共20 分;
第五組測試資料m, n =3,000,-9 ≤ score ≤ 9 ,共20 分。

Problem Source

臺北市103 學年度高級中學資訊學科能力競賽程式設計試題第二題
Set by Paupière
若測資有誤請儘快聯絡管管(?

Subtasks

No. Testdata Range Score
1 0~4 20
2 5~9 20
3 10~14 20
4 15~19 20
5 20~24 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 524288 262144 1
1 5000 524288 262144 1
2 5000 524288 262144 1
3 5000 524288 262144 1
4 5000 524288 262144 1
5 5000 524288 262144 2
6 5000 524288 262144 2
7 5000 524288 262144 2
8 5000 524288 262144 2
9 5000 524288 262144 2
10 5000 524288 262144 3
11 5000 524288 262144 3
12 5000 524288 262144 3
13 5000 524288 262144 3
14 5000 524288 262144 3
15 5000 524288 262144 4
16 5000 524288 262144 4
17 5000 524288 262144 4
18 5000 524288 262144 4
19 5000 524288 262144 4
20 5000 524288 262144 5
21 5000 524288 262144 5
22 5000 524288 262144 5
23 5000 524288 262144 5
24 5000 524288 262144 5