← 返回题目列表

AtCoder · pakencamp_2023_day1_p

P. MST(硬)

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

配点 : 600 点

問題文

长度 N 整数序列 A,B 。

頂点 u 和顶点 连接 v 的边的权重为 完整的图表是 A_u\times A_v + B_u \times B_v 求 G 的最小生成树的权重。 连接

制約

  • 2 \leq N \leq 5\times 10^4
  • |A_i|, |B_i| \le 10^6
  • 所有输入均为整数

入力

输入将以以下形式从标准输入给出。

N
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

出力

打印答案。 请创建一个输出


入力例 1

3
1 3 -1
-2 0 -4

出力例 1

0

頂点 1 和顶点 连接 2 的边的权重为 连接 1 \times 3 + (-2) \times 0 = 3 、

頂点 1 和顶点 连接 3 的边的权重为 连接 1 \times (-1) + (-2) \times (-4) = 7 、

頂点 2 和顶点 连接 3 的边的权重为 连接 3 \times (-1) + 0 \times (-4) = -3 。

因此 其被确定为 1 和 2 和的边 最少是创建一棵边连接 2 和 3 的生成树,这棵树的权重为 0 。


入力例 2

4
1 1 -1 -1
1 1 -1 -1

出力例 2

-6

(A_i, B_i) = (A_j, B_j) 变为 i, j (i \neq j) 也可能存在。 给出


入力例 3

10
-593389 -914534 -534565 -257272 -723595 763395 -272810 -869922 449729 -111959
743146 -30912 -528945 903153 -162840 -807868 227877 -433864 751438 34288

出力例 3

-5395522482698