分数: 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