790 . 幸運表格

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

aacpschool

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

33.3% (3/9)

Tags

apcsc apcsc-dp

Description

幸運表格，一個相傳能夠帶給人們幸運的表格。上面充滿了數字，獲得表格的人可以隨機從某個位置出發，並且持續不斷地向右或向下移動直到離開表格為止，而他所獲得的幸運指數即為經過的所有數字相加。
以下列表格為例：

-1 7 -8 10 -5
-4 -9 8 -6 0
5 -2 -6 -6 7
-7 4 7 -3 -3
7 1 -6 4 -9

若你從左上角開始，沿著右、下、下、右、右、右、右移動，則你將獲得 $-1+7-9-2-6-6+7=-10$ 的幸運指數。

請注意，這只是舉例如何計算幸運指數，不代表這個表格的最大幸運指數為 $-10$。

這個表格的最大幸運指數應為從第三列第一欄開始，沿著右、下、右、右、下、下移動，你可以獲得 $15$ 的幸運指數。

Input Format

輸入第一行有兩個正整數 $N,M(1 \leq N,M \leq 1000)$。
之後有 $N$ 行，每行有 $M$ 個數字 $a_{ij}(-100 \leq a_{ij} \leq 100)$ 用來描述該表格。

Output Format

請輸出一個整數，代表該表格所能帶給人的最大幸運指數。

Sample Input 1

2 2
5 -2
-3 1

Sample Output 1

4

Sample Input 2

5 5
-1 7 -8 10 -5
-4 -9 8 -6 0
5 -2 -6 -6 7
-7 4 7 -3 -3
7 1 -6 4 -9

Sample Output 2

15

Hints

Problem Source

2018 北市賽

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~20 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
16 2000 524288 65536 2
17 2000 524288 65536 2
18 2000 524288 65536 2
19 2000 524288 65536 2
20 2000 524288 65536 2
Submit
Back to Top