레이팅 미적용Architect Hrvoje has been tasked with drawing a large irregular wall composed
of vertical columns.
The wall consists of \(n\) columns placed next to each other, where the \(i\)-th column
has height \(a_{i}\) and width 1. In order to make the drawing as complicated as possible,
the \(i\)-th column is divided into \(b_{i}\) parts of equal height.
Hrvoje has only a ruler and a pencil at his disposal. With one stroke of the pencil
he can draw one line segment (a straight line between two points) without lifting
the pencil. His goal is to draw the entire wall, including all column edges and all
boundaries between their divisions, using as few line segments as possible.
For the given wall, output the minimum number of line segments that need to be drawn in order to draw
the wall completely.
The first line contains a natural number \(n\) (\(1 \le n \le 10^{5}\)), the number from the problem statement.
The second line contains a sequence of \(n\) numbers \(1 \le a_{i} \le 10^{9}\), from the problem statement.
The third line contains a sequence of \(n\) numbers \(1 \le b_{i} \le 10^{9}\), from the problem statement.
In the first and only line output one number – the minimum number of line segments Hrvoje needs to
draw to draw the wall.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 11점 | \(N = 1\) |
2 | 13점 | \(N = 2\), \(1 \le a_{i}\), \(b_{i} \le 10\) |
3 | 29점 | \(1 \le a_{i} \le 10^{6}\), \(b_{i}\) divides \(a_{i}\) for every \(1 \le i \le n\) |
4 | 57점 | No additional constraints. |
3
4 6 4
2 3 4103
4 6 3
3 3 212
Pojašnjenje drugog probnog primjera: Hrvoje will extend the topmost line segment in the first
column into the second column and thus “merge” 2 line segments into one. He will do the same with the
3 line segments at the bottom of the wall. This way, he will draw a total of 12 line segments, and it can
be shown that this is the minimum number of line segments that Hrvoje needs to draw.