← 返回题目列表

AtCoder · abc407_g

G. 多米诺骨牌覆盖 SUM

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个网格 H 行和 W 列。 让 (i,j) 表示位于 i从顶部算起的第行 (1\leq i\leq H) 和 j左起第 列 (1\leq j\leq W).

细胞 (i,j)\ (1\leq i\leq H,1\leq j\leq W) 有一个整数 A_{i,j} 。

让我们在网格上放置零个或多个多米诺骨牌。 多米诺骨牌覆盖两个相邻的单元格,即以下对之一:

  • 细胞 (i,j) 和 (i,j+1) 为 1\leq i\leq H,1\leq j\lt W;
  • 细胞 (i,j) 和 (i+1,j) 为 1\leq i\lt H,1\leq j\leq W.

任何单元格都不能被多于一张多米诺骨牌覆盖。

对于多米诺骨牌的放置,定义其 分数 作为单元格中写入的所有整数的总和 不 被任何多米诺骨牌覆盖。

找到可能的最大分数。

约束

  • 1\leq H
  • 1\leq W
  • HW\leq2000
  • -10 ^ {12}\leq A _ {i,j}\leq10 ^ {12}\ (1\leq i\leq H,1\leq j\leq W)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

H W
A _ {1,1} A _ {1,2} \ldots A _ {1,W}
A _ {2,1} A _ {2,2} \ldots A _ {2,W}
\vdots
A _ {H,1} A _ {H,2} \ldots A _ {H,W}

输出

输出答案。


示例输入 1

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

示例输出 1

23

网格如下:

例如,以下位置的得分为 23.

没有任何展示位置得分达到 24 或更高,因此输出 23.


示例输入 2

5 5
-70 11 -45 -54 -30
-99 39 -83 -69 -77
-48 -21 -43 -96 -24
-54 -65 21 -88 -44
-90 -33 -67 -29 -62

示例输出 2

39

示例输入 3

8 9
-74832 16944 58683 32965 97236 -52995 43262 -51959 40883
-58715 13846 24919 65627 -11492 -63264 29966 -98452 -75577
40415 77202 15542 -50602 83295 85415 -35304 46520 -38742
37482 56721 -38521 63127 55608 95115 42893 10484 70510
53019 40623 25885 -10246 70973 32528 -33423 19322 52097
79880 74931 -58277 -33783 91022 -53003 11085 -65924 -63548
78622 -77307 81181 46875 -81091 63881 11160 -82217 -55492
62770 39530 -95923 92440 -69899 77737 89392 -14281 84899

示例输出 3

2232232