{"problem":{"name":"[GESP202406 五级] 黑白格","description":{"content":"小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。 小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10719"},"statements":[{"statement_type":"Markdown","content":"小杨有一个 $n$ 行 $m$ 列的网格图，其中每个格子要么是白色，要么是黑色。\n\n小杨想知道至少包含 $k$ 个黑色格子的最小子矩形包含了多少个格子。\n\n## Input\n\n第一行包含三个正整数 $n,m,k$，含义如题面所示。\n\n之后 $n$ 行，每行⼀个长度为 $m$ 的 $\\texttt{01}$ 串，代表网格图第 $i$ 行格子的颜色，如果为 $\\texttt{0}$，则对应格子为白色，否则为黑色。\n\n## Output\n\n输出一个整数，代表至少包含 $k$ 个黑色格子的最小子矩形包含格子的数量，如果不存在则输出 $0$。\n\n[samples]\n\n## Background\n\n对应的选择、判断题：<https://ti.luogu.com.cn/problemset/1153>\n\n## Note\n\n#### 样例解释\n\n对于样例 $1$，假设 $(i,j)$ 代表第 $i$ 行第 $j$ 列，至少包含 $5$ 个黑色格子的最小子矩形的四个顶点为 $(2,4)$，$(2,5)$，$(4,4)$，$(4,5)$，共包含 $6$ 个格子。\n\n#### 数据范围\n\n对于全部数据，保证有 $1\\le n,m\\le 100$，$1\\le k\\le n\\times m$。\n\n| 子任务编号 | 得分 | $n,m$ |\n| :--: | :--: | :--: |\n| $1$ | $20$ | $\\le 10$  |\n| $2$ | $40$ | $n=1$，$1\\le m\\le 100$ |\n| $3$ | $40$ | $\\le 100$|\n\nUpdate on 2024/7/9：添加了若干组 hack 数据，感谢 @cff_0102 的贡献。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10719","tags":["数学","二分","2024","前缀和","GESP"],"sample_group":[["4 5 5\n00000\n01111\n00011\n00011","6"]],"created_at":"2026-03-03 11:09:25"}}