014 - We Used to Sing a Song Together(★3)
Editorial
Time Limit: 2 sec / Memory Limit: 1024 MB
配点: 点
問題文
AGC 街道には 人の小学生が住んでおり、小学生 の家は位置 にあります。
また、小学校は 校建てられており、小学校 は位置 にあります。
AGC 街道に住む小学生は性格が悪く、どの人同士も険悪な関係になっているため、全員が別の学校に通うようにしたいです。
また、不便さは次のように定義されます。
- 小学生 にとっての家から学校までの距離を とするとき、不便さは距離の総和、すなわち である。
- ただし、位置 から位置 までの距離は
どの生徒も別の学校に通うという条件下における、不便さとして考えられる最小値を求めてください。
制約
- は相異なる
- は相異なる
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられます。
出力
答えを出力してください。
入力例 1Copy
Copy
1 869 120
出力例 1Copy
Copy
749
小学生 の家と小学校 の距離は です。
この入力では小学生 が必ず小学校 に通うことになるため、この値が不便さとして考えられる唯一の値であり、最小値です。
入力例 2Copy
Copy
6 8 6 9 1 2 0 1 5 7 2 3 9
出力例 2Copy
Copy
5
小学生 をそれぞれ小学校 に通わせることにすると、不便さは となります。
これ以上不便さを小さくすることはできないため、答えは です。
入力例 3Copy
Copy
10 31 41 59 26 53 58 97 93 23 84 17 32 5 8 7 56 88 77 29 35
出力例 3Copy
Copy
211
入力例 4Copy
Copy
20 804289382 846930886 681692776 714636914 957747792 424238335 719885386 649760491 596516649 189641420 25202361 350490026 783368690 102520058 44897761 967513925 365180539 540383425 304089172 303455735 35005211 521595368 294702567 726956428 336465782 861021530 278722862 233665123 145174065 468703135 101513928 801979801 315634021 635723058 369133068 125898166 59961392 89018454 628175011 656478041
出力例 4Copy
Copy
2736647674