/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は山岳リゾートの開発責任者です。彼は N 個の展望スポットを結ぶ観光ルートを設計しようとしています。
それぞれの展望スポットには「標高」が設定されており、 i 番目の展望スポットの標高は整数 A_i メートルです。高橋君は、これらの展望スポットを一列に並べて観光ルートを作成します。
このリゾートでは、隣り合う2つの展望スポットの間に「吊り橋」を架けることができます。吊り橋を架けた箇所では、その両端の展望スポットの標高差の絶対値が「スリル値」として加算されます。標高差が大きいほど、観光客にとって魅力的な吊り橋となるためです。
高橋君は、 N 個の展望スポットを好きな順番に並べ替えた上で、隣り合う展望スポットの間のうちちょうど K 箇所に吊り橋を架けます。このとき、観光ルート全体の「スリル値」の合計を最大化したいと考えています。
展望スポットの並べ方と吊り橋を架ける箇所を最適に選んだとき、「スリル値」の合計の最大値を求めてください。
制約
- 2 \leq N \leq 10^6
- 1 \leq K \leq N - 1
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、展望スポットの数を表す N 、吊り橋を架ける箇所の数を表す K が、スペース区切りで与えられる。
- 2 行目には、各展望スポットの標高を表す A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
「スリル値」の合計の最大値を 1 行で出力せよ。
入力例 1
4 2 1 5 3 9
出力例 1
14
入力例 2
5 1 10 10 1 7 4
出力例 2
9
入力例 3
10 4 12 45 7 30 18 60 3 25 50 9
出力例 3
198
入力例 4
20 10 100 5 250 80 999 430 12 700 65 321 888 45 560 210 777 34 600 150 920 1
出力例 4
8354
入力例 5
2 1 1 1000000000
出力例 5
999999999
Score : 400 pts
Problem Statement
Takahashi is the development manager of a mountain resort. He is trying to design a sightseeing route connecting N observation spots.
Each observation spot has an "elevation" assigned to it, and the elevation of the i-th observation spot is an integer A_i meters. Takahashi will arrange these observation spots in a line to create a sightseeing route.
In this resort, a "suspension bridge" can be built between two adjacent observation spots. At a location where a suspension bridge is built, the absolute value of the elevation difference between the two observation spots at its endpoints is added as the "thrill value". This is because the greater the elevation difference, the more attractive the suspension bridge is to tourists.
Takahashi will rearrange the N observation spots in any order he likes, and then build suspension bridges at exactly K locations among the gaps between adjacent observation spots. He wants to maximize the total "thrill value" of the entire sightseeing route.
When the arrangement of observation spots and the locations of suspension bridges are chosen optimally, find the maximum possible total "thrill value".
Constraints
- 2 \leq N \leq 10^6
- 1 \leq K \leq N - 1
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains N, the number of observation spots, and K, the number of locations where suspension bridges are built, separated by a space.
- The second line contains A_1, A_2, \ldots, A_N, the elevations of each observation spot, separated by spaces.
Output
Output the maximum possible total "thrill value" in one line.
Sample Input 1
4 2 1 5 3 9
Sample Output 1
14
Sample Input 2
5 1 10 10 1 7 4
Sample Output 2
9
Sample Input 3
10 4 12 45 7 30 18 60 3 25 50 9
Sample Output 3
198
Sample Input 4
20 10 100 5 250 80 999 430 12 700 65 321 888 45 560 210 777 34 600 150 920 1
Sample Output 4
8354
Sample Input 5
2 1 1 1000000000
Sample Output 5
999999999