TopCoder

User's AC Ratio

97.6% (40/41)

Submission's AC Ratio

62.4% (103/165)

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

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