← 返回题目列表

AtCoder · abc406_g

G. 旅行商问题

中文机器翻译题面 查看原题

分数: 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