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

[语言月赛202303] Carrot Harvest G

题目描述

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

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

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

输入格式

输入共 n+1n + 1 行。

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

第二行至第 n+1n + 1 行,每行 mm 个只可能为 00 或 11 的整数。其中第 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

题目来源:洛谷 B3724