No.3604 Min of Max of Div of Sum
kazuppa
ぽえ問題文
正整数 $N$ と 正整数列 $(A_1,A_2,\dotsc,A_N)\ ,\ (B_1,B_2,\dotsc,B_N)$ が与えられます。
$\displaystyle\min_{1\leq k\leq N} \max_{1\leq l\leq k\leq r\leq N} \frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}$ を求めてください。
制約
- $1\leq N\leq 10^5$
- $1\leq A_i,B_i\leq 10^9$
- 入力はすべて整数
入力
$N$ $A_1\ A_2\ \dotsc\ A_N$ $B_1\ B_2\ \dotsc\ B_N$
出力
答えを一行に出力してください。
真の解との絶対誤差または相対誤差が $10^{-6}$ 以下のとき正解と判定されます。
サンプル
サンプル1
入力
3 1 2 3 3 2 1
出力
1
$k=1$ のとき、条件を満たす $(l,r)$ は $(1,1),(1,2),(1,3)$ であり、これらの $\frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}$ は $\frac{1}{3},\frac{3}{5},1$ のため、$\displaystyle\max_{1\leq l\leq k\leq r\leq N} \frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}=1$ です。
$k=2$ のとき、条件を満たす $(l,r)$ は $(1,2),(1,3),(2,2),(2,3)$ であり、これらの $\frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}$ は $\frac{3}{5},1,1,\frac{5}{3}$ のため、$\displaystyle\max_{1\leq l\leq k\leq r\leq N} \frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}=\frac{5}{3}$ です。
$k=3$ のとき、条件を満たす $(l,r)$ は $(1,3),(2,3),(3,3)$ であり、これらの $\frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}$ は $1,\frac{5}{3},3$ のため、$\displaystyle\max_{1\leq l\leq k\leq r\leq N} \frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}=3$ です。
よって、答えは $\min(1,\frac{5}{3},3)=1$ なので、$1$ を出力してください。
サンプル2
入力
3 999999998 999999999 1000000000 3 2 1
出力
499999999.5
サンプル3
入力
6 1 6 9 2 3 1 4 1 1 8 9 2
出力
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。