← 返回题目列表

AtCoder · arc194_c

C. 翻转成本

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

分数: 600 点

问题陈述

给定两个长度的整数序列 N, A = (A_1, A_2, \ldots, A_N) 和 B = (B_1, B_2, \ldots, B_N),每个由 0 和 1.

您可以对 A 任意次数(可能为零):

  1. 首先,选择一个整数 i 满意 1 \leq i \leq N,并翻转值 A_i (如果原始值为 0,将其更改为 1;如果是的话 1,将其更改为 0).
  2. 然后,付款 \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