题目内容

在收集相机应用的自动对焦系统中，画面被划分为 $m \times n$ 个对焦区域，每个区域的对比度用一个整数表示。现在需要选择一个面积恰好为 maxArea 的矩形区域，使其平均对比度值最大。

定义：选取一个 $h$ 行 $\times$ $w$ 列的连续矩形区域 $R$（$h \times w = \text{maxArea}$，且矩形须完全位于矩阵内），其平均对比度为

其中求和范围为区域 $R$ 内的所有格子 $(i, j)$。由于面积固定为 maxArea，分母是常数，因此

「平均对比度值最大」等价于「矩形区域内对比度求和最大」。

请返回所有合法矩形中 $\text{avg}(R)$ 的最大值，保留 5 位小数。

输入描述

输入只有一行，形如：

[[1,2,3],[4,5,6]],2

即先用一对方括号包住整个矩阵：行与行之间用 ],[ 分隔，同一行内的元素之间用半角逗号分隔，逗号后不带空格；矩阵的方括号之后紧跟一个半角逗号，再给出整数 maxArea。

m 与 n 不在输入中单独给出：$m$ 等于矩阵的行数，$n$ 等于每一行的元素个数（各行元素个数相同）。读入代码应能容忍逗号/方括号前后的多余空白。

取值范围：

1. $1 \le m, n \le 350$，其中 $m$ 为矩阵行数、$n$ 为矩阵列数；
2. $0 \le \text{contrastMatrix}[i][j] \le 255$；
3. $1 \le \text{maxArea} \le m \times n$，且保证至少存在一个能放进矩阵的 $h \times w$，即存在因子 $h \mid \text{maxArea}$ 使 $h \le m$ 且 $\text{maxArea}/h \le n$。

输出描述

输出一行，为最大平均对比度，格式固定为「整数部分 + 小数点 + 恰好 5 位小数」，第 6 位小数四舍五入，位数不足时补 0。

例如 5.50000、40.00000、116.66667。评测按逐字节一致比对，请勿输出多余空格、单位或换行之外的字符。

样例1

输入

[[1,2,3],[4,5,6]],2

输出

5.50000

说明

面积必须恰好为 2，可行的尺寸只有 $1 \times 2$ 与 $2 \times 1$：

• 选第 2 行的 [5,6]，平均值 $=(5+6)/2=5.5$；
• 或 [2,3]，平均值 $=2.5$；
• 或 [4,5]，平均值 $=4.5$；
• $2 \times 1$ 的最佳是第 3 列的 (3,6)，和 $=9$，平均值 $=4.5$。

最大为 $5.5$，按格式返回 5.50000。

样例2

输入

[[10,20],[30,40]],1

输出

40.00000

说明

maxArea = 1，只能选单个格子，最大值是 $40$，按格式返回 40.00000。

样例3

输入

[[100,50,200],[150,80,120]],3

输出

116.66667

说明

面积恰好为 3，可选 $1 \times 3$ 或 $3 \times 1$。矩阵是 2 行 3 列，$3 \times 1$ 需要 3 行，放不下，所以只能选 $1 \times 3$：

• 第 1 行 [100,50,200]：$350/3 \approx 116.66667$；
• 第 2 行 [150,80,120]：$350/3 \approx 116.66667$。

最大为 $116.66667$。

说明

• 原题在平台上标记了 Special Judge（浮点比较）；本仓库的测例用精确输出代替：标准答案的 5 位小数形式是唯一的，评测按逐字节一致比对。
• 时间限制 2 秒，空间限制 512 MB。
• 本题算法标签：前缀和。