C - Adventure of Collecting Gems Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は N 行 M 列のマス目で表されるダンジョンを探索しています。上から i 行目、左から j 列目のマスを (i, j) と表します。各マス (i, j)（1 \leq i \leq N, 1 \leq j \leq M）には宝石が 1 つ置かれており、その価値は A_{i,j} です。

高橋君は現在、ダンジョンの左上のマス (1, 1) にいます。ゴールである右下のマス (N, M) まで移動したいと考えています。高橋君は 1 回の移動で、現在いるマスから右に隣接するマスまたは下に隣接するマスへ 1 マスだけ進むことができます。すなわち、マス (i, j) からはマス (i, j+1)（j + 1 \leq M のとき）またはマス (i+1, j)（i + 1 \leq N のとき）へ移動できます。

高橋君は、通過するすべてのマス（始点 (1, 1) および終点 (N, M) を含む）に置かれている宝石を回収します。

高橋君は、回収する宝石の価値の合計を最大化したいと考えています。(1, 1) から (N, M) まで移動するすべての経路のうち、通過するマスの宝石の価値の合計が最大となる値を求めて出力してください。

制約

  • 1 \leq N \leq 1000
  • 1 \leq M \leq 1000
  • 0 \leq A_{i,j} \leq 10^9
  • 入力はすべて整数

入力

N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
  • 1 行目には、ダンジョンの行数を表す整数 N と列数を表す整数 M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、マス目の i 行目の各マスの宝石の価値 A_{i,1}, A_{i,2}, \ldots, A_{i,M} がスペース区切りで与えられる。

出力

高橋君が回収できる宝石の価値の合計の最大値を 1 行で出力してください。

入力例 1

3 3
1 2 3
4 5 6
7 8 9

出力例 1

29

入力例 2

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

出力例 2

54

入力例 3

6 8
100 200 50 300 10 400 150 80
250 30 500 20 600 70 90 200
80 700 100 800 50 300 400 100
150 60 900 200 100 1000 50 350
300 400 50 150 200 80 600 700
100 200 300 400 500 600 700 800

出力例 3

5610

Score : 366 pts

Problem Statement

Takahashi is exploring a dungeon represented as a grid with N rows and M columns. The cell at the i-th row from the top and the j-th column from the left is denoted as (i, j). Each cell (i, j) (1 \leq i \leq N, 1 \leq j \leq M) contains one gem with a value of A_{i,j}.

Takahashi is currently at the top-left cell (1, 1) of the dungeon. He wants to move to the bottom-right cell (N, M), which is the goal. In one move, Takahashi can advance exactly one cell to the right-adjacent cell or the down-adjacent cell from his current cell. That is, from cell (i, j), he can move to cell (i, j+1) (when j + 1 \leq M) or cell (i+1, j) (when i + 1 \leq N).

Takahashi collects the gems placed on all cells he passes through (including the starting cell (1, 1) and the ending cell (N, M)).

Takahashi wants to maximize the total value of the gems he collects. Among all paths from (1, 1) to (N, M), find and output the maximum possible total value of gems on the cells along the path.

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq M \leq 1000
  • 0 \leq A_{i,j} \leq 10^9
  • All input values are integers.

Input

N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
  • The first line contains an integer N representing the number of rows and an integer M representing the number of columns of the dungeon, separated by a space.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the gem values A_{i,1}, A_{i,2}, \ldots, A_{i,M} of each cell in the i-th row of the grid, separated by spaces.

Output

Output the maximum total value of gems that Takahashi can collect, on a single line.

Sample Input 1

3 3
1 2 3
4 5 6
7 8 9

Sample Output 1

29

Sample Input 2

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

Sample Output 2

54

Sample Input 3

6 8
100 200 50 300 10 400 150 80
250 30 500 20 600 70 90 200
80 700 100 800 50 300 400 100
150 60 900 200 100 1000 50 350
300 400 50 150 200 80 600 700
100 200 300 400 500 600 700 800

Sample Output 3

5610