torus711 のアレ

主に競技プログラミングの問題について書きます

Codeforces #203, Division 2, A : TL

概要

コンテストの問題の Time Limit を設定したい。
n 個の想定解と、m 個の想定 TLE 解があり、それぞれの実行時間は a_ib_i である。
次の条件を満たす 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