#P18933. [2026多校联测]舞台
[2026多校联测]舞台
舞台
题目描述
你有 行 列的一个舞台,第 行第 列的格子上写有一个整数 。
你需要分别将每个格子涂上红、橙、黄、绿四种颜色之一,我们称满足如下要求的染色方案是简单的:
- 红色格子的上方是红色格子,左边是红色或黄色格子,右边是红色或橙色格子。
- 橙色格子的右边是橙色格子,上方是橙色或红色格子,下方是橙色或绿色格子。
- 绿色格子的下方是绿色格子,右边是绿色或橙色格子,左边是绿色或黄色格子。
- 黄色格子的左边是黄色格子,下方是黄色或绿色格子,上方是黄色或红色格子。

上图中展示了一些可能的染色方案,其中:
- 第一幅图是简单的。
- 第二幅图是简单的。
- 第三幅图不是简单的。
若 的颜色为红、橙、黄、绿,则这个格子的权值 分别为 。计算所有简单的方案中,$\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j} w_{i,j}$ 的最大值。
输入格式
输入的第一行包含两个正整数 ,表示舞台的行数和列数。
之后有 行,每行 个整数。第 行第 个整数表示 。
本题读入量较大,建议使用较快的读入方式
输出格式
输出一行一个整数表示答案。
样例 1 输入
3 4
8 -2 -5 7
-4 6 -1 -3
5 1 4 3
样例 1 输出
87
样例解释 1

染色方案如上图所示。
样例 2
见选手目录下的 stage2.in 与 stage2.ans。
样例 3
见选手目录下的 stage3.in 与 stage3.ans。
样例 4
见选手目录下的 stage4.in 与 stage4.ans。
数据范围
对于所有测试数据,保证:,。
| 测试点编号 | 特殊性质 | |
|---|---|---|
| 无 | ||
| ^ | ||
| A | ||
| ^ | 无 |
- 特殊性质 A:。