{"problem":{"name":"[语言月赛 202307] 魔法少女扶苏","description":{"content":"给定一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列的数称为 $a_{i,j}$。 扶苏可以释放任意多次魔法，每次施放魔法，矩阵里的**每个**数字都会被减去 $1$。 现在扶苏想知道，她至少需要释放几次魔法，才能让矩阵中存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y}$ 大于或等于它所在行和列的元素之和。 形式化地，你需要计算最小的魔法释放次数使得施","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGB3811"},"statements":[{"statement_type":"Markdown","content":"给定一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列的数称为 $a_{i,j}$。\n\n扶苏可以释放任意多次魔法，每次施放魔法，矩阵里的**每个**数字都会被减去 $1$。\n\n现在扶苏想知道，她至少需要释放几次魔法，才能让矩阵中存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y}$ 大于或等于它所在行和列的元素之和。\n\n形式化地，你需要计算最小的魔法释放次数使得施放魔法后存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y} \\geq \\sum \\limits _{i = 1}^n a_{i,y} + \\sum \\limits _{i = 1}^m a_{x,i}$。\n\n## Input\n\n第一行是三个整数，表示矩阵的行数 $n$，列数 $m$ 和要求符合条件的位置个数 $k$。\n\n接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行的第 $j$ 个整数表示初始的 $a_{i,j}$。\n\n## Output\n\n输出一行一个整数表示答案。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n释放 $3$ 次魔法后，矩阵变为\n\n$$\\begin{matrix}-2 & -1 & 0\\\\1& 2&3\\\\\\end{matrix}$$\n\n于是 $a_{1,1} = -2 > (-1) + (-3) = \\sum\\limits_{i =1}^n a_{i,1} + \\sum\\limits_{i = 1}^m a_{1, i}$。\n\n### 数据规模与约定\n\n- 对 $20\\%$ 的数据，$n = 1$。\n- 另有 $20\\%$ 的数据，$m = 1$。\n- 对 $70\\%$ 的数据，$n, m \\leq 10$，$a_i \\leq 100$。\n- 对 $100\\%$ 的数据，保证 $1 \\leq n, m \\leq 100$，$1 \\leq k \\leq n \\times m$，$1 \\leq a_i \\leq 10^{4}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGB3811","tags":["2023","O2优化","数组","语言月赛"],"sample_group":[["2 3 1\n1 2 3\n4 5 6\n","3"]],"created_at":"2026-03-03 11:09:25"}}