No.3604 Min of Max of Div of Sum
kazuppa
ぽえProblem Statement
You are given a positive integer $N$ and sequences of positive integers $(A_1,A_2,\dotsc,A_N)\ ,\ (B_1,B_2,\dotsc,B_N)$.
Find $\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}$.
Constraints
- $1\leq N\leq 10^5$
- $1\leq A_i,B_i\leq 10^9$
- All input values are integers.
Input
$N$ $A_1\ A_2\ \dotsc\ A_N$ $B_1\ B_2\ \dotsc\ B_N$
Output
Output the answer on one line.
Your answer is judged as correct if its absolute or relative error from the true value is at most $10^{-6}$.
Sample
Sample 1
Input
3 1 2 3 3 2 1
Output
1
For $k=1$, the pairs $(l,r)$ satisfying the condition are $(1,1),(1,2),(1,3)$, and their values of $\frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}$ are $\frac{1}{3},\frac{3}{5},1$, so $\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$.
For $k=2$, the pairs $(l,r)$ satisfying the condition are $(1,2),(1,3),(2,2),(2,3)$, and their values of $\frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}$ are $\frac{3}{5},1,1,\frac{5}{3}$, so $\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}$.
For $k=3$, the pairs $(l,r)$ satisfying the condition are $(1,3),(2,3),(3,3)$, and their values of $\frac{\sum_{i=l}^r A_i}{\sum_{i=l}^r B_i}$ are $1,\frac{5}{3},3$, so $\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$.
Therefore, the answer is $\min(1,\frac{5}{3},3)=1$, so output $1$.
Sample 2
Input
3 999999998 999999999 1000000000 3 2 1
Output
499999999.5
Sample 3
Input
6 1 6 9 2 3 1 4 1 1 8 9 2
Output
1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。