[NOISG 2022 Qualification] L-Board

ID: 10819

远端评测题

2000ms

1024MiB

难度: 4

上传者:

标签>

动态规划 DP

2022

前缀和

NOISG（新加坡）

题目背景

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}

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

2 2
8 1
3 4

1 8
-2 -1 8 -2 9 0 -2 1

【样例解释】

对于样例 $1$ ，选择点 $(1,1)$ , $(2,1)$ , $(1,2)$ ，覆盖的数字为 $8, 3, 4$ ，总和为 $15$ 。

对于样例 $2$ ，选择点 $(1,3)$ , $(1,5)$ , $(1,3)$ ，形成一条直线，覆盖的数字为 $8, -2, 9$ ，总和为 $15$ 。

【数据范围】