[入门赛 #14] 魔法少女扶苏 (Hard Version)

Luogu

IDLGP9457

Time1500ms

Memory512MB

DifficultyP3

2023O2优化语言月赛

给定一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列的数称为 $a_{i,j}$。扶苏可以释放任意多次魔法，每次施放魔法，矩阵里的**每个**数字都会被减去 $1$。现在扶苏想知道，她至少需要释放几次魔法，才能让矩阵中存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y}$ 大于或等于它所在行和列的元素之和。形式化地，你需要计算最小的魔法释放次数使得施放魔法后存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y} \geq \sum \limits _{i = 1}^n a_{i,y} + \sum \limits _{i = 1}^m a_{x,i}$。 ## Input 第一行是三个整数，表示矩阵的行数 $n$，列数 $m$ 和要求符合条件的位置个数 $k$。接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行的第 $j$ 个整数表示初始的 $a_{i,j}$。 ## Output 输出一行一个整数表示答案。 [samples] ## Note ### 样例 1 解释释放 $3$ 次魔法后，矩阵变为 $$\begin{matrix}-2 & -1 & 0\\1& 2&3\\\end{matrix}$$ 于是 $a_{1,1} = -2 > (-1) + (-3) = \sum\limits_{i =1}^n a_{i,1} + \sum\limits_{i = 1}^m a_{1, i}$。 ### 数据规模与约定 - 对 $100\%$ 的数据，保证 $1 \leq n, m \leq 3 \times 10^3$，$1 \leq k \leq n \times m$，$0 \leq a_i \leq 10^{11}$。 ### 提示 **请使用合理的读入方式，避免超时。**

Samples

Input #1

2 3 1
1 2 3
4 5 6

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[入门赛 #14] 魔法少女扶苏 (Hard Version)",
    "description": {
      "content": "给定一个 $n$ 行 $m$ 列的数字矩阵，第 $i$ 行第 $j$ 列的数称为 $a_{i,j}$。 扶苏可以释放任意多次魔法，每次施放魔法，矩阵里的**每个**数字都会被减去 $1$。 现在扶苏想知道，她至少需要释放几次魔法，才能让矩阵中存在至少 $k$ 个位置 $(x, y)$，满足 $a_{x, y}$ 大于或等于它所在行和列的元素之和。 形式化地，你需要计算最小的魔法释放次数使得施",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9457"
  },
  "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形式化地，你需要计算最小的魔法释放次数使得施...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments