{"problem":{"name":"[语言月赛202303] Carrot Harvest G","description":{"content":"有 $n$ 行 $m$ 列共 $n \\times m$ 个坑，每个坑可能有一个萝卜，也可能没有。 现在 Farmer John 需要至少拔 $k$ 个萝卜，他只能挑一个矩形（长方形或正方形）区域的坑进行拔萝卜。 请你求出，为了至少拔 $k$ 个萝卜，他需要挑的矩形面积（坑的数量）最小是多少。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P1"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3724"},"statements":[{"statement_type":"Markdown","content":"有 $n$ 行 $m$ 列共 $n \\times m$ 个坑，每个坑可能有一个萝卜，也可能没有。\n\n现在 Farmer John 需要至少拔 $k$ 个萝卜，他只能挑一个矩形（长方形或正方形）区域的坑进行拔萝卜。\n\n请你求出，为了至少拔 $k$ 个萝卜，他需要挑的矩形面积（坑的数量）最小是多少。\n\n## Input\n\n输入共 $n + 1$ 行。\n\n第一行为三个整数 $n, m, k$。\n\n第二行至第 $n + 1$ 行，每行 $m$ 个只可能为 $0$ 或 $1$ 的整数。其中第 $i + 1$ 行的第 $j$ 个整数为 $a _ {i, j}$，代表第 $i$ 行第 $j$ 列的坑中是否有萝卜。$a _ {i, j} = 1$ 代表有萝卜，$a _ {i, j} = 0$ 代表没有萝卜。\n\n## Output\n\n输出共一行一个整数，代表为了至少拔 $k$ 个萝卜，Farmer John 需要挑的矩形的最小面积（坑的数量）。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n如下图所示，绿色底色的方格为有萝卜的区域，白色底色的方格为无萝卜的区域。红色框起的区域为一种拔萝卜的区域，使用 $8$ 的面积拔了 $7$ 个萝卜。可以证明不存在工作面积更小的拔萝卜方式。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/63u88gjp.png)\n\n### 数据规模与约定\n\n对于 $100\\%$ 的数据，保证 $1 \\leq n, m \\leq 20$，$1 \\leq k \\leq 400$。\n\n| 测试点编号 | $n$ | $m$ | $k$ |\n| :----------: | :----------: | :----------: | :----------: |\n| $2$ | $= 2$ | $= 2$ | $= 1$ |\n| $3, 4$ | $= 2$ | $= 2$ | $\\leq 4$ |\n| $5$ | $\\leq 20$ | $= 1$ | $\\leq 400$ |\n| $6, 7$ | $\\leq 20$ | $= 2$ | $\\leq 400$ |\n| $1, 8, 9, 10$ | $\\leq 20$ | $\\leq 20$ | $\\leq 400$ |\n\n数据保证一定有至少一种拔萝卜的方式可以拔至少 $k$ 个萝卜。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3724","tags":["2023","O2优化","循环结构","语言月赛"],"sample_group":[["5 5 7\n0 0 0 1 0\n0 0 1 1 1\n0 1 1 1 1\n0 1 1 0 0\n0 0 0 0 1","8"]],"created_at":"2026-03-03 11:09:25"}}