| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 121 | 60 | 40 | 53.333% |
신촌 왕국은 현재 재개발 공사가 한창이다. 일렬로 된 도로에 $N$개의 전봇대가 설치되어 있는데, 이 중 일부를 제거하고 사이를 전깃줄로 연결하는 작업이다. 전봇대를 순서대로 1ドル$번부터 $N$번이라고 했을 때, 1ドル$번 전봇대 아래에 있는 발전소로부터 $N$번 전봇대 아래에 있는 마을에 전력을 공급해야 한다. 두 전봇대 사이에 전깃줄이 없으면 전기가 흐르지 않는다.
어떤 $i$번 전봇대와 $j$번 전봇대$(1 \le i < j \le N)$ 사이에 전깃줄을 설치하는 비용은 다음과 같다.
$$ C_i - 2 \cdot \gcd(C_i, C_{i+1}, \dots, C_j) + C_j $$
단, 전깃줄을 설치하려면 먼저 그 사이에 있는 전봇대를 모두 제거해야 한다. 이때 $i$번째 전봇대를 제거하는 비용은 $B_i$이다. 당연하게도 1ドル$번 전봇대에서 $N$번 전봇대까지 연결하는 비용을 최소로 만들고 싶다. 신촌 왕국을 도와 최소 비용으로 전깃줄 작업을 진행해보자!
첫 번째 줄에 $N$이 주어진다. $(2 \le N \le 200,000円)$
두 번째 줄에 정수 $C_1, C_2, \dots, C_N$이 공백으로 구분되어 주어진다. $(1 \le C_i \le 10^9)$
세 번째 줄에 정수 $B_1, B_2, \dots, B_N$이 공백으로 구분되어 주어진다. $(1 \le B_i \le 10^9)$
1ドル$번 전봇대에서 $N$번 전봇대까지 연결하는 최소 비용을 출력한다.
6 50 4 32 12 20 6 7 4 5 50 30 16
107
3ドル$번, 5ドル$번 전봇대를 제거하는 비용이 35ドル$이고 1ドル$번, 2ドル$번, 4ドル$번, 6ドル$번 사이 전깃줄을 설치하는 비용이 72ドル$이다. 총 비용은 107ドル$로 이 경우가 최소이다.