分数: 600 点
问题陈述
给定两个长度的整数序列 N, A = (A_1, A_2, \ldots, A_N) 和 B = (B_1, B_2, \ldots, B_N),每个由 0 和 1.
您可以对 A 任意次数(可能为零):
- 首先,选择一个整数 i 满意 1 \leq i \leq N,并翻转值 A_i (如果原始值为 0,将其更改为 1;如果是的话 1,将其更改为 0).
- 然后,付款 \sum_{k=1}^N A_k C_k 日元作为此操作的成本。
请注意,步骤 2 中的成本计算使用 步骤 1 中更改后的 A 。
打印制作所需的最低总成本 A 相同于 B.
约束
- 1 \leq N \leq 2 \times 10^5
- A_i, B_i \in {0, 1}
- 1 \leq C_i \leq 10^6
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N C_1 C_2 \ldots C_N
输出
打印答案。
示例输入 1
4 0 1 1 1 1 0 1 0 4 6 2 9
示例输出 1
16
考虑以下过程:
- 一、翻转 A_4。现在, A = (0, 1, 1, 0)。该操作的成本是 0 \times 4 + 1 \times 6 + 1 \times 2 + 0 \times 9 = 8 日元。
- 接下来,翻转 A_2。现在, A = (0, 0, 1, 0)。该操作的成本是 0 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 2 日元。
- 最后,翻转 A_1。现在, A = (1, 0, 1, 0),匹配 B。该操作的成本是 1 \times 4 + 0 \times 6 + 1 \times 2 + 0 \times 9 = 6 日元。
在这种情况下,总成本是 8 + 2 + 6 = 16 日元,这是可能的最低金额。
示例输入 2
5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
示例输出 2
0
A 和 B 最初已经相同,因此无需执行任何操作。
示例输入 3
20 1 1 1 1 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 0 0 1 0 1 0 0 52 73 97 72 54 15 79 67 13 55 65 22 36 90 84 46 1 2 27 8
示例输出 3
2867