← 返回题目列表

Codeforces · 187/E

E. 天堂之旅

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

故事并没有像 PMP 想象的那样结束。老天爷给了他一次重生的机会。但在他回来之前,上帝告诉他,PMP应该向包括杰出程序员在内的n位伟人询问他们的人生经历。

这些人站成一条直线。它们从左到右编号为 1 到 n。第 i 个人的坐标是 xi (xi < xi + 1, i < n)。 PMP 应该以任意顺序一一拜访所有这些人。每个人都应该被拜访一次。在他的旅行开始时,他从某个人的位置出发,询问他的经历。

每次PMP想要改变他的位置时,他应该给天使一张票,然后天使把他带到目的地。天使从一个地点带走 PMP,飞到他的目的地并将他放在那里。在这次运动中没有其他人被拜访过。从第 i 个人移动到第 j 个人,需要 |xi - xj|时间。 PMP一拜访众男就能起死回生。

有两种类型的天使:有些天使是往右边走的,他们只接受右边的票。其他人走左边,他们只接受左边的票。每种类型的天使数量无限。 PMP 有 l 个左票和 n - 1 - l 个右票。

PMP希望尽快复活,能够参加今年的决赛,而不是去年错过的决赛。他想知道怎样才能最快地拜访所有的人一次。他还需要知道他应该采取的确切顺序动作。

输入

输入的第一行包含三个空格分隔的整数 n、l、s (2 ≤ n ≤ 105, 0 ≤ l < n, 1 ≤ s ≤ n) — 参观人数、PMP 获得的剩余门票数量以及 PMP 的初始位置。下一行包含 n 个空格分隔的整数。该行中的第 i 个整数是 xi (0 = x1 < x2 < ... < xn ≤ 109) — 第 i 个人的位置。

输出

如果 PMP 无法使用票证拜访所有人员,他将在唯一的输出行中打印 -1。否则,您应该在第一行打印 PMP 可以访问所有男性的最短时间。在第二行中,您应该打印 n - 1 个整数,这些整数是 PMP 在一个最佳解决方案中应按顺序访问的人员数量。如果有多个答案,则输出其中任何一个。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。

示例

输入 #1

5 2 2
0 10 11 21 22

输出 #1

33
1 3 5 4

输入 #2

4 3 1
0 1 2 3

输出 #2

-1

输入 #3

7 3 2
0 100 200 201 301 303 305

输出 #3

409
1 3 4 7 6 5

注意

让我们在这里提醒一下,一位有史以来伟大的选手,大约一年前离开了我们。愿雷纳特·穆拉哈诺夫安息。