分数: 625 点
问题陈述
你和 N 商人站在数轴上。商户已编号 1, 2, \ldots, N.
最初,您位于坐标 0,以及商家 i 位于坐标处 X_i。 每个商人持有一件物品;商人持有的物品 i 称为项目 i.
你的目标是接收物品 1, 2, \ldots, N 按此顺序。
您可以按任意顺序重复以下三个操作任意次数:
- 移动自己 1。该操作的成本是 C.
- 选择一个商家并将该商家移动 1。该操作的成本是 D.
- 选择一个商家,例如商家 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
输出
输出两行。
第一行应包含实现目标所需的最小总成本。
第二行应包含 N 整数 A_1, A_2, \ldots, A_N 以空格分隔。这里,必须存在满足以下两个条件的操作序列:
- 目标已实现,且总成本尽可能最低。
- 对于每个整数 i 这样 1 \leq i \leq N,您收到物品 i 位于坐标处 A_i.
示例输入 1
3 2 3 1 -1 2
示例输出 1
10 0 0 2
例如,以下操作序列以总成本实现目标 10:
- 移动商家 1 来自坐标 1 to 0。该操作的成本是 3.
- 移动商家 2 来自坐标 -1 to 0。该操作的成本是 3.
- 接收物品 1 来自商家 1。该操作的成本是 0.
- 接收物品 2 来自商家 2。该操作的成本是 0.
- 将自己移出坐标 0 to 1。该操作的成本是 2.
- 将自己移出坐标 1 to 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