← 返回题目列表

AtCoder · pakencamp_2023_day2_d

D. 许多地下城

中文机器翻译题面 查看原题

配点 : 700 点

問題文

Mr.X 正在玩游戏,即将 征服 M 地下城。

每个地牢都是 N 由层次结构组成。地牢 i 可以得到第 j \ (1 \leq j \leq N) 等级制度有力量 有一只 A_{i,j} 怪兽。 Mr.X是一个地牢 按如下方式征服 x \ (1 \leq x \leq M) 。

  1. 地牢 x 进入时的初始健康状况 定义 h_x 。这里 必须满足 \displaystyle h_x > \max_{i=1}^{N} A_{x, i} 。
  2. 地牢 x 层次结构 输入 1 。 对于
  3. i = 1, 2, \cdots ,N ,层次结构如下: 征服 i 。你目前的体力 u 。
    1. u \leq A_{x, i} ,复活物品 1 次 将层次结构替换为 u 该值应乘以 h_x 变为。
    2. u 该值应乘以 u - A_{x, i} 继续 i + 1 。然而 当 i = N 时结束策略。

X先生的账户等级为 L 因此,在确定初始健康状况时 必须满足 \displaystyle \sum_{i=1}^{M} h_i \leq L 。另外, 在考虑每个 M 地下城中使用的复活物品数量时,我希望保持最大值尽可能小。在确定满足条件的初始生命值时,找到每个副本中使用的复活物品最大数量的最小值。

制約

  • 1 \leq N \leq 3 \times 10^4
  • 1 \leq M \leq 10^2
  • 1 \leq A_{i, j} \leq 10^9
  • \displaystyle \sum_{i=1}^{M} (\max_{j=1}^{N} A_{i, j} + 1) \leq L \leq 10^{18}
  • 所有输入均为整数

配点

分数由以下子作业确定。

  1. (200 点) N \leq 3 \times 10^3
  2. (500 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。 (注:由于限制,输入量较大,要注意速度。)

M N L
A_{1, 1} A_{1, 2} \cdots A_{1, N}
A_{2, 1} A_{2, 2} \cdots A_{2, N}
\vdots
A_{M, 1} A_{M, 2} \cdots A_{M, N}

出力

将您的答案打印在一行上。考虑到这个问题的限制,可以证明总有一种方法可以确定Mr.X能够征服所有地下城的初始体力强度。


入力例 1

3 3 24
5 2 3
9 3 7
3 7 1

出力例 1

2

h = (6, 10, 8) 然后地牢 1 有复活物品。 1 剩余的地下城里有复活物品。 2 需要一个,这是最佳的。


入力例 2

5 10 132
6 9 11 9 6 10 5 5 4 11
20 20 5 14 17 9 15 14 20 8
18 17 1 20 8 5 1 8 2 9
5 6 1 2 2 6 1 2 2 1
12 4 13 2 5 15 20 4 4 12

出力例 2

3