#P18933. [2026多校联测]舞台

[2026多校联测]舞台

舞台

题目描述

你有 nn 行 mm 列的一个舞台,第 ii 行第 jj 列的格子上写有一个整数 ai,ja_{i,j}。

你需要分别将每个格子涂上红、橙、黄、绿四种颜色之一,我们称满足如下要求的染色方案是简单的:

  • 红色格子的上方是红色格子,左边是红色或黄色格子,右边是红色或橙色格子。
  • 橙色格子的右边是橙色格子,上方是橙色或红色格子,下方是橙色或绿色格子。
  • 绿色格子的下方是绿色格子,右边是绿色或橙色格子,左边是绿色或黄色格子。
  • 黄色格子的左边是黄色格子,下方是黄色或绿色格子,上方是黄色或红色格子。

上图中展示了一些可能的染色方案,其中:

  • 第一幅图是简单的。
  • 第二幅图是简单的。
  • 第三幅图不是简单的。

若 (i,j)(i,j) 的颜色为红、橙、黄、绿,则这个格子的权值 wi,jw_{i,j} 分别为 1,2,3,41,2,3,4。计算所有简单的方案中,$\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j} w_{i,j}$ 的最大值。

输入格式

输入的第一行包含两个正整数 n,mn,m,表示舞台的行数和列数。

之后有 nn 行,每行 mm 个整数。第 ii 行第 jj 个整数表示 ai,ja_{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。

数据范围

对于所有测试数据,保证:1≤n,m≤20001 \le n,m \le 2000,∣ai,j∣≤109\lvert a_{i,j}\rvert \le 10^9。

测试点编号 n,m≤n,m\le 特殊性质
1∼31\sim 3 44 无
4∼64\sim 6 1010 ^
7∼117\sim 11 500500
12,1312,13 20002000 A
14∼2014\sim 20 ^ 无
  • 特殊性质 A:ai,j≥0a_{i,j}\ge 0。