No.031 D

得られた経験値を $e$, 使ったお金を $m$ として $x = e/m$ とおくと, $e - mx \geq 0$ となる最大の $x$ を求める問題となる.

これを最小カット問題に帰着させる.

条件は以下のようになる.

• $i$ 番目の経験値をもらうと $0$ かかる. もらわないと $S_i$ かかる. (最小を求めるので逆にする)
• $j$ 番目のアイテムを買うと $T_i/x$ かかる. 買わないと $0$ かかる.
• $j$ 番目のアイテムを買わないとき, $j$ 番目のアイテムが必要な $i$ 番目の経験値をもらうと $\infty$ かかる.

これをグラフにすると, 以下のようになる.

• ソースから $i$ 番目の経験値に $0$ の辺を, $i$ 番目の経験値からシンクに $S_i$ の辺を張る.
• ソースから $j$ 番目のアイテムに $T_i/x$ の辺を, $j$ 番目のアイテムからシンクに $0$ の辺を張る.
• $j$ 番目のアイテムから $j$ 番目のアイテムが必要な $i$ 番目の経験値に $\infty$ の辺を張る.

このグラフの最小カットを Dinic 法などで求める. この最小カットは $F = \sum S_i - e + mx$ なので, $e - mx \geq 0$ であるためには $F \geq \sum S_i$ であればいい.

ただし, 誤差によって最大フローが $\sum S_i$ より微妙に小さくなる可能性がある. そこで, $10^6$ 倍した値で計算して最後に $10^6$ で割って答えとする.