AT_abc225_g [ABC225G] X

题目描述

有一个高为 $H$ 行、宽为 $W$ 列的网格。每个格子里写有一个整数，对于从上往下第 $i$ 行、从左往右第 $j$ 列的格子 $(i,j)$，写有 $A_{i,j}$。

现在高桥君可以从 $H \times W$ 个格子中选择 $0$ 个或多个格子，在这些格子上画上“叉号”。每个“叉号”由两条线段组成，分别连接该格子的左上角与右下角，以及右上角与左下角。

高桥君的得分定义为：（被画上“叉号”的格子中所写整数的总和）减去 $C$ 乘以（画出这些“叉号”所需线段的最小数量）。

这里，高桥君可以将斜向相邻的格子的“叉号”连续画在一起。

例如，当在格子 $(1,1)$ 和格子 $(2,2)$ 上画“叉号”时，高桥君可以用以下 $3$ 条线段完成：

• 一条连接格子 $(1,1)$ 的左上角和格子 $(2,2)$ 的右下角的线段
• 一条连接格子 $(1,1)$ 的右上角和格子 $(1,1)$ 的左下角的线段
• 一条连接格子 $(2,2)$ 的右上角和格子 $(2,2)$ 的左下角的线段

请你求出高桥君的最大得分。注意，没有画“叉号”的格子上不能画任何东西。

输入格式

输入按以下格式从标准输入读入。

$H$ $W$ $C$
$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

输入 #1

2 2 2
2 10
8 3

输出 #1

12

输入输出样例 #2

输入 #2

3 3 100
1 1 1
1 1 1
1 1 1

输出 #2

0

输入输出样例 #3

输入 #3

8 9 970861213
1313462 943495812 203775264 839015475 115668311 14701110 819458175 827176922 236492592
843915104 786367010 344840288 618248834 824858165 549189141 120648070 805825275 933750119
709330492 38579914 890555497 75314343 238373458 854061807 637519536 53226153 627677130
671706386 380984116 221773266 787763728 639374738 298691145 359138139 183373508 524415106
716502263 150803008 390520954 913021901 553285119 876389099 952721235 46809105 635239775
355621458 511843148 117663063 37274476 891025941 832254337 346436418 783134705 488516288
383723241 322408013 948364423 409068145 120813872 697127655 968230339 988041557 222591780
712959990 233114128 210373172 798667159 568746366 579461421 923556823 777007925 422249456

输出 #3

9785518299

说明/提示

限制条件

• $1 \leq H, W \leq 100$
• $1 \leq C \leq 10^9$
• $1 \leq A_{i,j} \leq 10^9$
• 输入均为整数

样例解释 1

如果在格子 $(1,2)$ 和格子 $(2,1)$ 上画“叉号”，高桥君可以用以下 $3$ 条线段完成：

• 一条连接格子 $(1,2)$ 的左上角和格子 $(1,2)$ 的右下角的线段
• 一条连接格子 $(2,1)$ 的左上角和格子 $(2,1)$ 的右下角的线段
• 一条连接格子 $(1,2)$ 的右上角和格子 $(2,1)$ 的左下角的线段

因此，这种情况下的得分为 $10+8-2\times 3=12$。不存在比这更高的得分方案，所以答案为 $12$。

样例解释 2

不在任何格子上画“叉号”是最优的。

由 ChatGPT 4.1 翻译