{"problem":{"name":"[蓝桥杯 2022 省 B] 统计子矩阵","description":{"content":"给定一个 $N \\times M$ 的矩阵 $A$，请你统计有多少个子矩阵 (最小 $1 \\times 1$, 最大 $N \\times M$）满足子矩阵中所有数的和不超过给定的整数 $K$。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8783"},"statements":[{"statement_type":"Markdown","content":"给定一个 $N \\times M$ 的矩阵 $A$，请你统计有多少个子矩阵 (最小 $1 \\times 1$, 最大 $N \\times M$）满足子矩阵中所有数的和不超过给定的整数 $K$。\n\n## Input\n\n第一行包含三个整数 $N, M$ 和 $K$。\n\n之后 $N$ 行每行包含 $M$ 个整数, 代表矩阵 $A$。\n\n## Output\n\n一个整数代表答案。\n\n[samples]\n\n## Note\n\n**【样例说明】**\n\n满足条件的子矩阵一共有 $19$ 个，包含:\n\n大小为 $1 \\times 1$ 的有 $10$ 个。\n\n大小为 $1 \\times 2$ 的有 $3$ 个。 \n\n大小为 $1 \\times 3$ 的有 $2$ 个。\n\n大小为 $1 \\times 4$ 的有 $1$ 个。\n\n大小为 $2 \\times 1$ 的有 $3$ 个。\n\n**【评测用例规模与约定】**\n\n对于 $30 \\%$ 的数据，$N, M \\leq 20$.\n\n对于 $70 \\%$ 的数据，$N, M \\leq 100$.\n\n对于 $100 \\%$ 的数据，$1 \\leq N, M \\leq 500,0 \\leq A_{i j} \\leq 1000,1 \\leq K \\leq 2.5\\times10^8$. \n\n蓝桥杯 2022 省赛 B 组 F 题。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8783","tags":["2022","枚举","双指针 two-pointer","蓝桥杯省赛"],"sample_group":[["3 4 10\n1 2 3 4\n5 6 7 8\n9 10 11 12","19"]],"created_at":"2026-03-03 11:09:25"}}