#G1052. [GESP202406 五级] 黑白格

[GESP202406 五级] 黑白格

[GESP202406 五级] 黑白格

题目描述

小杨有一个 nn 行 mm 列的网格图,其中每个格子要么是白色,要么是黑色。

小杨想知道至少包含 kk 个黑色格子的最小子矩形包含了多少个格子。

输入格式

第一行包含三个正整数 n,m,kn, m, k,含义如题面所示。

之后 nn 行,每行一个长度为 mm 的 01 串,代表网格图第 ii 行格子的颜色,如果为 0,则对应格子为白色,否则为黑色。

输出格式

输出一个整数,代表至少包含 kk 个黑色格子的最小子矩形包含格子的数量,如果不存在则输出 0。

样例 #1

样例输入 #1

4 5 5
00000
01111
00011
00011

样例输出 #1

6

样例解释

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

数据范围

子任务编号 数据点占比 n,mn, m
1 20% n,m≤10n, m ≤ 10
2 40% n=1n = 1,1≤m≤1001 ≤ m ≤ 100
3 n,m≤100n, m ≤ 100
  • 对于全部数据,保证有 1≤n,m≤1001 ≤ n, m ≤ 100,1≤k≤n×m1 ≤ k ≤ n \times m。

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