概要
コンテストの問題の Time Limit を設定したい。
n 個の想定解と、m 個の想定 TLE 解があり、それぞれの実行時間は と
である。
次の条件を満たす TL の内、最小のものを求めよ。
存在しない場合は -1 で示せ。
- 全ての想定解は間に合う
- 想定解の内一つ以上は、その所要時間が a のとき、2a <= v を満たす
- 全ての想定 TLE 解は間に合わない
解法
v の下限は max( as の最小値 × 2, as の最大値 ) です。
また上限は bs の最大値 - 1 です。
下限 ≦ 上限 を満たすとき、下限が v の最小値になります。
そうでないとき解はありません。
コード
main = do getLine as <- map read . words <$> getLine bs <- map read . words <$> getLine let lb = max ( 2 * minimum as ) ( maximum as ) ub = minimum bs print $ if lb < ub then lb else -1
