分数: 2400 点
问题陈述
整数序列 A, B 和 C,每个长度 N,给出。 当且仅当满足以下条件时 Snuke 才是快乐的。
- 对于每个整数 x, \sum_{1 \leq i \leq N} |A_i-x| \leq \sum_{1 \leq i \leq N} |B_i-x| 成立。
他决定至少改变 0 的元素 A 变得快乐。 这让他付出了代价 C_i \times (A_i-t)^2 更改 A_i to t。 在这里, t,更改后的值应该是 整数 也是如此。
找出使 Snuke 变得快乐的最小可能成本总和。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 2 \times 10^5
- 0 \leq B_i \leq 2 \times 10^5
- 1 \leq C_i \leq 5
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N C_1 C_2 \cdots C_N
输出
打印答案。
示例输入 1
3 0 1 4 1 2 3 1 3 2
示例输出 1
6
经过以下操作,成本总和为 6.
- 更改 A_1 to 2。这个改变需要花费 1 \times (0-2)^2=4.
- 更改 A_3 to 3。这个改变需要花费 2 \times (4-3)^2=2.
操作后, A=(2,1,3) 成立,这让 Snuke 很高兴。 成本总和小于以下的目标是不可能实现的 6,所以答案是 6.
示例输入 2
20 185 89 216 105 56 383 193 161 75 196 322 180 390 15 206 78 275 338 225 167 161 77 294 117 22 382 218 140 57 231 343 160 397 8 264 68 301 349 295 157 3 1 3 5 2 1 3 4 1 4 2 2 2 2 5 1 1 5 4 3
示例输出 2
3758
示例输入 3
1 0 0 1
示例输出 3
0