第13547题 程序题
黑白格:寻找至少包含k个黑色格子的最小子矩形

时间限制: 1.0 s
内存限制: 512.0 MB

题面描述

小杨有一个$n$行$m$列的网格图,其中每个格子要么是白色,要么是黑色。
请计算至少包含$k$个黑色格子的最小子矩形包含多少个格子,如果不存在符合要求的子矩形则输出0。

输入格式

第一行包含三个正整数$n$,$m$,$k$,含义如题面所示。
之后$n$行,每行一个长度为$m$的01串,代表网格图第i行格子的颜色,0对应白色,1对应黑色。

输出格式

输出一个整数,代表答案。

样例输入

4 5 5
00000
01111
00011
00011

样例输出

6

样例解释

对于样例1,假设 $(i,j)$ 代表第i行第j列,至少包含5个黑色格子的最小子矩形的四个顶点为 (2,4),(2,5),(4,4),(4,5),共包含6个格子。

数据范围

对于全部数据,保证有$1 \le n,m \le 100$,$1 \le k \le n \times m$。

编辑模式