월간 향유회

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	1024 MB	349	106	88	41.706%

문제

$N$개의 정수로 이루어진 두 배열 $A$, $B$와 두 정수 $U$, $D$가 주어진다. 배열 $A$, $B$의 $i$번째 원소는 각각 $A_i$, $B_i$이다.

$f(n)$을 다음과 같이 정의한다.

아래 과정을 $i = 1, 2, \cdots, n$에 대해 순서대로 수행한다.
1. $A_i$와 $B_i$ 중 하나를 고른다.
2. 이후 $i < j \le n$을 만족하는 모든 $j$에 대해, $A_i$를 골랐다면 $A_j$와 $B_j$의 값이 $U$만큼 증가하고, $B_i$를 골랐다면 $A_j$와 $B_j$의 값이 $D$만큼 감소한다.
$f(n)$은 수를 고르는 $2^n$가지 방법 중, 고른 수들의 합의 최솟값이다.

$1$ 이상 $N$ 이하의 모든 정수 $n$에 대해, $f(n)$의 값을 구해보자.

첫째 줄에 배열의 길이 $N$과 양의 정수 $U$, $D$가 공백으로 구분되어 주어진다. $(1 \le N \le 300\ 000$; $1 \le U, D \le 10^6)$

둘째 줄에 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(0 \le A_i \le 10^6)$

셋째 줄에 $B_1, B_2, \cdots, B_N$이 공백으로 구분되어 주어진다. $(0 \le B_i \le 10^6)$

$N$개의 줄에 걸쳐 답을 출력한다. $n$번째 줄에는 $f(n)$을 출력한다.

5 2 3
4 8 2 8 1
11 5 14 8 19

$f(5)$의 값을 얻을 수 있는 방법은 다음과 같다.

$A_1 = 4$, $B_1 = 11$ 중 $B_1$를 고른다. 이후 수열 $A$는 $[4, \color{red}{5}, \color{red}{-1}, \color{red}{5}, \color{red}{-2}]$, $B$는 $[11, \color{red}{2}, \color{red}{11}, \color{red}{5}, \color{red}{16}]$로 변한다.
$A_2 = 5$, $B_2 = 2$ 중 $B_2$를 고른다. 이후 수열 $A$는 $[4, 5, \color{red}{-4}, \color{red}{2}, \color{red}{-5}]$, $B$는 $[11, 2, \color{red}{8}, \color{red}{2}, \color{red}{13}]$로 변한다.
$A_3 = -4$, $B_3 = 8$ 중 $A_3$를 고른다. 이후 수열 $A$는 $[4, 5, -4, \color{blue}{4}, \color{blue}{-3}]$, $B$는 $[11, 2, 8, \color{blue}{4}, \color{blue}{15}]$로 변한다.
$A_4 = 4$, $B_4 = 4$ 중 $B_4$를 고른다. 이후 수열 $A$는 $[4, 5, -4, 4, \color{red}{-6}]$, $B$는 $[11, 2, 8, 4, \color{red}{12}]$로 변한다.
$A_5 = -6$, $B_5 = 12$ 중 $A_5$를 고른다.

고른 수들의 합은 $11 + 2 + (-4) + 4 + (-6) = 7$이다.

Contest > BOJ User Contest > 월간 향유회 > 월간 향유회 2024. 09. A번