/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 625 点
問題文
数直線上にあなたと N 人の商人がいます。商人には 1, 2, \ldots, N の番号が付けられています。
はじめ、あなたは座標 0 におり、商人 i は座標 X_i にいます。また、各商人は品物を 1 つずつ持っており、商人 i が持っている品物を品物 i と表記します。
あなたの目的は、品物 1, 2, \ldots, N をこの順に受け取ることです。
あなたは、以下の 3 つの操作を好きな順序で好きな回数繰り返すことができます。
- 自分が 1 移動する。この操作にはコストが C かかる。
- 商人を 1 人選び、選んだ商人に 1 移動してもらう。この操作にはコストが D かかる。
- 商人を 1 人選び、選んだ商人を商人 i とする。あなたと商人 i のいる座標が一致しており、あなたが商人 i から品物を受け取ったことがない場合、商人 i から品物 i を受け取る。そうでない場合、何もしない。この操作にはコストが 0 かかる。
目的を達成するためにかかるコストの合計の最小値を求めてください。
また、目的を達成するためにかかるコストの合計を最小化したときに各商人から品物を受け取る座標として考えられるもののうちのひとつを求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C, D \leq 10^5
- -10^5 \leq X_i \leq 10^5
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N C D X_1 X_2 \ldots X_N
出力
2 行出力せよ。
1 行目には目的を達成するためにかかるコストの合計の最小値を出力せよ。
2 行目には、N 個の整数 A_1, A_2, \ldots, A_N をこの順に空白区切りで出力せよ。ただし、ある操作列が存在し、この操作列において以下の条件がともに満たされているようにせよ。
- 目的を達成しており、目的を達成するという条件のもとコストの合計は最小である。
- 1 \leq i \leq N なるすべての整数 i に対して商人 i から 座標 A_i で品物を受け取っている。
入力例 1
3 2 3 1 -1 2
出力例 1
10 0 0 2
例えば以下のように操作をすることで、コストの合計を 10 として目的を達成することができます。
- 商人 1 に座標 1 から座標 0 に移動してもらう。この操作にはコストが 3 かかる。
- 商人 2 に座標 -1 から座標 0 に移動してもらう。この操作にはコストが 3 かかる。
- 商人 1 から品物 1 を受け取る。この操作にはコストが 0 かかる。
- 商人 2 から品物 2 を受け取る。この操作にはコストが 0 かかる。
- あなたが座標 0 から座標 1 に移動する。この操作にはコストが 2 かかる。
- あなたが座標 1 から座標 2 に移動する。この操作にはコストが 2 かかる。
- 商人 3 から品物 3 を受け取る。この操作にはコストが 0 かかる。
コストの合計を 10 未満として目的を達成することはできません。
入力例 2
2 100000 60000 100000 -100000
出力例 2
12000000000 0 0
入力例 3
6 4 4 2 -1 5 -2 -2 2
出力例 3
56 0 -1 -1 -2 -2 2
Score : 625 points
Problem Statement
You and N merchants stand on a number line. The merchants are numbered 1, 2, \ldots, N.
Initially, you are at coordinate 0, and merchant i is at coordinate X_i. Each merchant holds one item; the item held by merchant i is called item i.
Your goal is to receive items 1, 2, \ldots, N in this order.
You may repeat any number of times, in any order, the following three operations:
- Move yourself by 1. The cost of this operation is C.
- Choose one merchant and move that merchant by 1. The cost of this operation is D.
- Choose one merchant, say merchant i. If you and merchant i are at the same coordinate, and you have not yet received item i, then receive item i from merchant i. Otherwise, do nothing. The cost of this operation is 0.
Find the minimum total cost required to achieve the goal.
Also, output one possible combination of coordinates at which you receive each item when the total cost is minimized.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq C, D \leq 10^5
- -10^5 \leq X_i \leq 10^5
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N C D X_1 X_2 \ldots X_N
Output
Output two lines.
The first line should contain the minimal total cost required to achieve the goal.
The second line should contain N integers A_1, A_2, \ldots, A_N separated by spaces. Here, there must exist a sequence of operations that satisfies both of the following conditions:
- The goal is achieved, with the minimum possible total cost.
- For every integer i such that 1 \leq i \leq N, you receive item i at coordinate A_i.
Sample Input 1
3 2 3 1 -1 2
Sample Output 1
10 0 0 2
For example, the following sequence of operations achieves the goal with total cost 10:
- Move merchant 1 from coordinate 1 to 0. The cost of this operation is 3.
- Move merchant 2 from coordinate -1 to 0. The cost of this operation is 3.
- Receive item 1 from merchant 1. The cost of this operation is 0.
- Receive item 2 from merchant 2. The cost of this operation is 0.
- Move yourself from coordinate 0 to 1. The cost of this operation is 2.
- Move yourself from coordinate 1 to 2. The cost of this operation is 2.
- Receive item 3 from merchant 3. The cost of this operation is 0.
It is impossible to achieve the goal with total cost less than 10.
Sample Input 2
2 100000 60000 100000 -100000
Sample Output 2
12000000000 0 0
Sample Input 3
6 4 4 2 -1 5 -2 -2 2
Sample Output 3
56 0 -1 -1 -2 -2 2