← 返回题目列表

AtCoder · abc225_g

G. X形切割

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

分数: 600 点

问题陈述

我们有一个网格 H 水平行和 W 垂直列。每个方格包含一个整数。广场 (i, j) 在 i从顶部开始的第行和 j从左边算起的第列包含整数 A_{i,j}.

Takahashi 将从中选择零个或多个 H \times W 正方形并在每个正方形上画一个 X。 X 由连接左上角和右下角的线段以及连接右上角和左下角的线段组成。

让我们将高桥的分数定义为 (绘制 X 的方格中包含的整数之和) - C \times (绘制 X 所需的最小线段数).

在这里,Takahashi 可以一次在对角相邻的方块上画 X。

例如,他可以在方块上画 X (1, 1) 和 (2, 2) 包含三个部分:

  • 连接左上角的线段 (1, 1) 和右下角 (2, 2),
  • 连接右上角的线段 (1, 1) 和左下角 (1, 1),
  • 连接右上角的线段 (2, 2) 和左下角 (2, 2).

求高桥的最大可能得分。 请注意,不应在未选择的方块上绘制任何内容。

约束

  • 1 \leq H,W \leq 100
  • 1 \leq C \leq 10^9
  • 1 \leq A_{i,j} \leq 10^9
  • 输入中的所有值都是整数。

输入

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

H W C
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\hspace{1.5cm}\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}

输出

打印高桥的最大可能分数。


示例输入 1

2 2 2
2 10
8 3

示例输出 1

12

如果他选择了方块 (1,2) 和 (2,1),他可以用三段在上面画 X:

  • 连接左上角的线段 (1, 2) 和右下角 (1, 2),
  • 连接左上角的线段 (2, 1) 和右下角 (2, 1),
  • 连接右上角的线段 (1, 2) 和左下角 (2, 1).

因此,高桥的分数将为 10+8-2 \times 3=12.

没有办法标记获得严格更高分数的方块,所以答案是 12.


示例输入 2

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

示例输出 2

0

最好不要标记方块。


示例输入 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