G - MST (Easy)
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の整数列 A が与えられます。
頂点 u と頂点 v を結ぶ辺の重みが A_u\times A_v である完全グラフ G の最小全域木の重みを求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- |A_i| \le 10^6
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 1 2 3
出力例 1
5
頂点 1 と頂点 2 を結ぶ辺の重みは 1\times 2=2 、
頂点 1 と頂点 3 を結ぶ辺の重みは 1\times 3=3 、
頂点 2 と頂点 3 を結ぶ辺の重みは 2\times 3=6 です。
よって 1 と 2 を結ぶ辺、 1 と 3 を結ぶ辺で全域木を作るのが最小で、この木の重みは 5 になります。
入力例 2
4 1 1 -1 -1
出力例 2
-3