33742번 - Bracket Problem Yet Again 다국어

A balanced bracket string is a string consisting of '(' and ')', which can make a valid mathematical expression by inserting $0$ or $+$ in the string $0$ or more times.

Bob had learned how to find the balanced bracket string with minimum cost, when the cost is defined as follows.

• If position $i$ contains '(', the cost of the position is $a_i$;
• If position $i$ contains ')', the cost of the position is $b_i$;
• The cost of a balanced bracket string is the sum of costs of all positions.

While rethinking about the solution, Bob became curious about the following problem.

• Assuming I can make $a_i$ and $b_i$ both $0$ for at most $k$ different indices, what is the new minimum cost?

As he was unable to solve the modified problem, he asked you to solve it. As Bob is a very selfish person, he wants you to solve it for each possible value of $k$. The indices chosen for $k=x$ need not be a strict subset of the indices chosen for $k=x+1$. In other words, the problem must be solved independently for all values of $k$.

The first line contains an even integer $n$, the length of the bracket sequence. ($2 \le n \le 2\cdot 10^5$)

The second line contains $n$ integers $a_1,a_2,\cdots,a_n$, the costs of using '(' on each index. ($0 \le a_i \le 10^9$)

The third line contains $n$ integers $b_1,b_2,\cdots,b_n$, the costs of using ')' on each index. ($0 \le b_i \le 10^9$)

Output $n+1$ integers $c_0,c_1,\cdots,c_n$ separated by spaces. $c_x$ is defined by the minimum cost of the problem when $k=x$.