No.2009 Drunkers' Contest
Problem Statement
Kiri-kun loves drinking programming contests.
A drinking programming contest is a contest in which you solve problems while drinking alcohol.
It is known that drinking alcohol clears the mind and so raises one's ability to come up with ideas, but it also increases mistakes and so lowers one's implementation ability.
This contest has a total of $N$ problems, from problem $1$ to problem $N$.
Kiri-kun solves these problems in order, starting from problem $1$.
Each problem is divided into an idea part and an implementation part. When he has drunk a cumulative total of $x$ of alcohol,
the time required for the $i\ (1\le i\le N)$-th problem is $\displaystyle\frac{A_i}{1+x}$ minutes for the idea part and $B_i(1+x)$ minutes for the implementation part.
Kiri-kun can drink as much alcohol as he likes before starting each problem.
Given that he starts the contest without having drunk any alcohol, find the minimum time required to finish solving all the problems.
The time it takes to drink alcohol can be ignored.
Input
$N$ $A_1\ A_2\ \cdots\ A_N$ $B_1\ B_2\ \cdots\ B_N$
All inputs are integers.
$1\le N\le 2\times 10^5$
$1\le A_i\le 10^9\ (1\le i\le N)$
$1\le B_i\le 10^9\ (1\le i\le N)$
Output
Output the answer. Your answer will be considered correct if its absolute or relative error from the correct answer is at most $10^{-6}$. Print a newline at the end.
Sample
Sample 1
Input
2 2 18 3 2
Output
17
It is optimal to drink no alcohol before starting problem 1, and to drink $2$ (corrected at 21:35) of alcohol before starting problem 2. In this case, problem 1 takes $2$ for the idea part and $3$ for the implementation part, for a total time of $5$. Problem 2 takes $18\div 3=6$ for the idea part and $2\times 3 = 6$ for the implementation part, for a total time of $12$. In total, all the problems can be solved in a time of $17$. The time cannot be made shorter than $17$, so printing 17 is correct.
Sample 2
Input
2 18 2 2 3
Output
20
The order of the problems is reversed from Sample 1. It is optimal to drink $1$ (corrected at 21:35) of alcohol first. In this case, problem 1 takes $18\div 2 = 9$ for the idea part and $2\times 2 = 4$ for the implementation part, for a total time of $13$, and problem 2 takes $2\div 2=1$ for the idea part and $3\times 2 = 6$ for the implementation part, for a total time of $7$, so the total time required is 20. Note that problem 2 cannot be solved first.
Sample 3
Input
1 2 1
Output
2.8284271247
It is optimal to drink $\sqrt2-1$ (corrected at 21:35) of alcohol before starting problem $1$, in which case the whole takes a time of $2\sqrt2$. Your answer will be considered correct if its absolute or relative error from the correct answer is at most $10^{-6}$.
Sample 4
Input
1 1 2
Output
3
It is optimal not to drink any alcohol at all.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kiri8128