P11293 [NOISG 2022 Qualification] L-Board

Lord Pooty 有一个 $n \times m$ 的整数棋盘 $A$。他希望在棋盘上画一个 L 型区域，并且希望覆盖的数字总和最大。L 型区域可以旋转 $4$ 种方向，且每一边不一定完整（可以是一条直线）。

给定一个 $n \times m$ 的棋盘 $A$，你需要选择棋盘上的三个点 $(x_1, y_1)$, $(x_2, y_1)$, $(x_1, y_2)$，使得以下公式的值 $V$ 最大化： $$ V = \sum_{i=\min(x_1,x_2)}^{\max(x_1,x_2)} A_{i,y_1} + \sum_{j=\min(y_1,y_2)}^{\max(y_1,y_2)} A_{x_1,j} - A_{x_1,y_1} $$

- 第一行包含两个整数 $n$ 和 $m$，分别表示棋盘的行数和列数。 - 接下来的 $n$ 行，每行包含 $m$ 个整数，表示棋盘的元素。

输出一个整数，即最大化的 $V$ 值。

【样例解释】 对于样例 $1$，选择点 $(1,1)$, $(2,1)$, $(1,2)$，覆盖的数字为 $8, 3, 4$，总和为 $15$。 对于样例 $2$，选择点 $(1,3)$, $(1,5)$, $(1,3)$，形成一条直线，覆盖的数字为 $8, -2, 9$，总和为 $15$。 【数据范围】 - $1 \leq n, m \leq 1000$ - $-10^9 \leq A_{i,j} \leq 10^9$ | 子任务编号 | 分值 | 额外限制条件 | | :--------: | :--: | :----------------------: | | $1$ | $5$ | $1 \leq n, m \leq 2$ | | $2$ | $10$ | $n = 1$ | | $3$ | $15$ | $1 \leq n, m \leq 100$ | | $4$ | $15$ | $1 \leq n, m \leq 300$ | | $5$ | $25$ | $0 \leq A_{i,j} \leq 10^9$ | | $6$ | $30$ | 无额外限制 |