#546. [语言月赛202303] Carrot Harvest G

[语言月赛202303] Carrot Harvest G

题目描述

nnmm 列共 n×mn \times m 个坑,每个坑可能有一个萝卜,也可能没有。

现在 Farmer John 需要至少拔 kk 个萝卜,他只能挑一个矩形(长方形或正方形)区域的坑进行拔萝卜。

请你求出,为了至少拔 kk 个萝卜,他需要挑的矩形面积(坑的数量)最小是多少。

输入格式

输入共 n+1n + 1 行。

第一行为三个整数 n,m,kn, m, k

第二行至第 n+1n + 1 行,每行 mm 个只可能为 0011 的整数。其中第 i+1i + 1 行的第 jj 个整数为 ai,ja _ {i, j},代表第 ii 行第 jj 列的坑中是否有萝卜。ai,j=1a _ {i, j} = 1 代表有萝卜,ai,j=0a _ {i, j} = 0 代表没有萝卜。

输出格式

输出共一行一个整数,代表为了至少拔 kk 个萝卜,Farmer John 需要挑的矩形的最小面积(坑的数量)。

5 5 7
0 0 0 1 0
0 0 1 1 1
0 1 1 1 1
0 1 1 0 0
0 0 0 0 1
8

提示

样例 1 解释

如下图所示,绿色底色的方格为有萝卜的区域,白色底色的方格为无萝卜的区域。红色框起的区域为一种拔萝卜的区域,使用 88 的面积拔了 77 个萝卜。可以证明不存在工作面积更小的拔萝卜方式。

数据规模与约定

对于 100%100\% 的数据,保证 1n,m201 \leq n, m \leq 201k4001 \leq k \leq 400

测试点编号 nn mm kk
22 =2= 2 =1= 1
3,43, 4 4\leq 4
55 20\leq 20 =1= 1 400\leq 400
6,76, 7 =2= 2
1,8,9,101, 8, 9, 10 20\leq 20

数据保证一定有至少一种拔萝卜的方式可以拔至少 kk 个萝卜。