33OJ
登录 注册

#P17737. [ICPC 2019 Xuzhou R] Factory

[ICPC 2019 Xuzhou R] Factory

题目描述

你拥有一家特殊的饮料厂,生产 NN 种饮料。

工厂里有 KK 台机器,每台机器都能生产所有 NN 种饮料。所有 KK 台机器可以并行工作。一台机器一次只能生产一种饮料,但机器可以在不同种类的饮料之间瞬间切换。

每台机器的生产能力不同。具体地,第 jj 台机器生产 rr 升第 ii 种饮料需要 r×tijr \times t_{ij} 分钟。饮料是连续生产的,因此 rr 可以是任意实数。

今天,你接到一份订单,需要每种饮料各 11 升。你想尽快完成生产。因此,请编写一个程序,计算完成生产所需的最短可能时间。

输入格式

第一行包含两个正整数 N,KN, K (N≤2×104N \le 2 \times 10^4, K≤50K \le 50) —— 饮料的种类数和机器的数量。

接下来的 NN 行,每行包含 KK 个整数。第 ii 行第 jj 个数为 tijt_{ij} (1≤tij≤501 \le t_{ij} \le 50)。

输出格式

输出一行一个实数,表示生产每种饮料各 11 升的最短时间。

若你的答案的相对误差不超过 10−210^{-2},则视为正确。

3 3
1 2 3
2 1 3
6 6 3
2.000000
5 2
1 7
3 9
4 10
5 11
6 12
12.687500

提示

翻译由 DeepSeek V4 Pro 完成