C - Ski Course Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、縦 N 行・横 M 列のグリッド状に区画されたスキー場にいます。各区画には、その区画を滑ったときに得られるスコア（正の整数）が設定されています。

高橋君は山頂（第 1 行）から山麓（第 N 行）まで滑り降りるコースを選びます。

コースの選び方は以下の規則に従います：

  • 第 1 行のいずれかの区画からスタートする。
  • 各行から次の行へ滑り降りる際、現在の位置を (r, c) とすると、次の行では (r+1, c-1) 、 (r+1, c) 、 (r+1, c+1) のいずれかの区画に移動できる。ただし、グリッドの範囲外には移動できない。
  • さらに、コースはジグザグ型でなければならない。すなわち、連続する 3 つの行における水平方向の移動（列の変化）を考えたとき、 2 回連続で同じ方向（左・左、または右・右）に移動することはない。具体的には、第 r 行から第 r+1 行への列の変化を d_r = c_{r+1} - c_r としたとき、 d_r > 0 かつ d_{r+1} > 0 となることはなく、 d_r < 0 かつ d_{r+1} < 0 となることもない。（ d_r = 0 の場合はどの方向への移動の後にも続けられる。）

高橋君は、コース上の区画のスコアの合計を最大化したいと考えています。条件を満たすジグザグ型のコースのうち、スコアの合計値の最大値を求めてください。

制約

  • 1 \leq N \leq 2000
  • 1 \leq M \leq 2000
  • N \times M \leq 2 \times 10^6
  • 1 \leq G_{i,j} \leq 10^9
  • 入力はすべて整数である。

入力

N M
G_{1,1} G_{1,2} \ldots G_{1,M}
G_{2,1} G_{2,2} \ldots G_{2,M}
\vdots
G_{N,1} G_{N,2} \ldots G_{N,M}
  • 1 行目には、グリッドの行数を表す N と列数を表す M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、グリッドの各行の値が与えられる。
  • 1 + i 行目（ 1 \leq i \leq N ）には、第 i 行の各区画のスコア G_{i,1}, G_{i,2}, \ldots, G_{i,M} がスペース区切りで与えられる。

出力

条件を満たすジグザグ型のコース上のスコアの合計値の最大値を 1 行で出力せよ。

入力例 1

3 3
5 1 4
2 10 3
7 6 8

出力例 1

22

入力例 2

4 4
1 100 1 1
1 1 100 1
1 1 1 100
50 1 50 1

出力例 2

251

入力例 3

6 7
12 7 30 4 18 25 9
5 40 8 22 6 13 17
19 3 35 10 28 2 14
8 16 11 45 7 20 5
23 9 27 6 33 12 18
4 31 15 24 10 29 21

出力例 3

183

入力例 4

10 10
45 12 78 34 56 23 89 11 67 40
18 95 27 63 14 72 31 50 86 9
54 20 88 17 69 42 10 97 36 61
73 28 15 91 33 64 22 80 47 6
11 58 39 24 99 16 70 43 85 32
66 8 52 77 21 94 35 13 60 48
29 83 5 68 41 26 90 19 74 37
96 44 30 7 55 81 12 62 25 71
38 59 92 46 3 75 49 87 20 14
82 36 65 53 79 27 57 4 98 33

出力例 4

796

入力例 5

1 1
1000000000

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi is at a ski resort divided into a grid of N rows and M columns. Each cell has a score (a positive integer) that is earned when skiing through that cell.

Takahashi chooses a course to ski down from the summit (row 1) to the base of the mountain (row N).

The course must be chosen according to the following rules:

  • Start from any cell in row 1.
  • When skiing from one row to the next, if the current position is (r, c), you can move to any of (r+1, c-1), (r+1, c), or (r+1, c+1) in the next row. However, you cannot move outside the grid.
  • Furthermore, the course must be zigzag-shaped. That is, when considering the horizontal movements (changes in column) over any three consecutive rows, you cannot move in the same direction (left-left, or right-right) two times in a row. Specifically, if we define the change in column from row r to row r+1 as d_r = c_{r+1} - c_r, then it is never the case that d_r > 0 and d_{r+1} > 0, nor is it ever the case that d_r < 0 and d_{r+1} < 0. (If d_r = 0, it can follow a movement in any direction.)

Takahashi wants to maximize the total score of the cells on his course. Among all valid zigzag-shaped courses, find the maximum total score.

Constraints

  • 1 \leq N \leq 2000
  • 1 \leq M \leq 2000
  • N \times M \leq 2 \times 10^6
  • 1 \leq G_{i,j} \leq 10^9
  • All input values are integers.

Input

N M
G_{1,1} G_{1,2} \ldots G_{1,M}
G_{2,1} G_{2,2} \ldots G_{2,M}
\vdots
G_{N,1} G_{N,2} \ldots G_{N,M}
  • The first line contains N, the number of rows, and M, the number of columns, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the values of each row of the grid are given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the scores G_{i,1}, G_{i,2}, \ldots, G_{i,M} of each cell in row i, separated by spaces.

Output

Output in one line the maximum total score of a valid zigzag-shaped course.

Sample Input 1

3 3
5 1 4
2 10 3
7 6 8

Sample Output 1

22

Sample Input 2

4 4
1 100 1 1
1 1 100 1
1 1 1 100
50 1 50 1

Sample Output 2

251

Sample Input 3

6 7
12 7 30 4 18 25 9
5 40 8 22 6 13 17
19 3 35 10 28 2 14
8 16 11 45 7 20 5
23 9 27 6 33 12 18
4 31 15 24 10 29 21

Sample Output 3

183

Sample Input 4

10 10
45 12 78 34 56 23 89 11 67 40
18 95 27 63 14 72 31 50 86 9
54 20 88 17 69 42 10 97 36 61
73 28 15 91 33 64 22 80 47 6
11 58 39 24 99 16 70 43 85 32
66 8 52 77 21 94 35 13 60 48
29 83 5 68 41 26 90 19 74 37
96 44 30 7 55 81 12 62 25 71
38 59 92 46 3 75 49 87 20 14
82 36 65 53 79 27 57 4 98 33

Sample Output 4

796

Sample Input 5

1 1
1000000000

Sample Output 5

1000000000