← 返回题目列表

AtCoder · abc232_f

I. 顺序的简单操作

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

分数: 500 点

问题陈述

给出两个序列 N 整数: A = (A_1, A_2, \ldots, A_N) 和 B = (B_1, B_2 \ldots, B_N).

关于顺序 A,您可以按任意顺序执行任意次数(可能为零)以下两个操作。

  • 选择一个整数 i 满意 1 \leq i \leq N,并增加或减少 A_i by 1,费用为 X 日元(日本货币)。
  • 选择一个整数 i 满意 1 \leq i \leq N-1,并交换值 A_i 和 A_{i+1},费用为 Y 日元。

打印完成序列所需的最小总成本 A 等于序列 B 重复上述操作。

约束

  • 2 \leq N \leq 18
  • 1 \leq X \leq 10^8
  • 1 \leq Y \leq 10^{16}
  • 1 \leq A_i, B_i \leq 10^8
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N X Y
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

输出

打印制作所需的最低总成本 A 等于 B.


示例输入 1

4 3 5
4 2 5 2
6 4 2 1

示例输出 1

16

最初,我们有 A = (4, 2, 5, 2).
以下操作顺序使得 A 等于 B.

  • 支付 X = 3 日元增加值 A_3 by 1, 制作 A = (4, 2, 6, 2).
  • 支付 Y = 5 日元交换以下值 A_2 和 A_3, 制作 A = (4, 6, 2, 2).
  • 支付 Y = 5 日元交换以下值 A_1 和 A_2, 制作 A = (6, 4, 2, 2).
  • 支付 X = 3 日元减少价值 A_4 by 1, 制作 A = (6, 4, 2, 1).

这些操作的总成本是 3+5+5+3 = 16 日元,这是可能的最低金额。


示例输入 2

5 12345 6789
1 2 3 4 5
1 2 3 4 5

示例输出 2

0

A 和 B 从一开始就相等,所以不需要任何操作。


示例输入 3

18 20719114 5117250357733867
10511029 36397527 63027379 44706927 47672230 79861204 57882493 42931589 51053644 52300688 43971370 26515475 62139996 41282303 34022578 12523039 6696497 64922712
14720753 4621362 25269832 91410838 86751784 32741849 6602693 60719353 28911226 88280613 18745325 80675202 34289776 37849132 99280042 73760634 43897718 40659077

示例输出 3

13104119429316474

请注意,输入或输出中的值可能不适合 32- 位整数类型。