Problem:


Score : 300 points

Problem Statement

We will play a one-player game using a number line and N pieces.

First, we place each of these pieces at some integer coordinate.

Here, multiple pieces can be placed at the same coordinate.

Our objective is to visit all of the M coordinates X_1, X_2, ..., X_M with these pieces, by repeating the following move:

Move: Choose a piece and let x be its coordinate. Put that piece at coordinate x+1 or x-1.

Note that the coordinates where we initially place the pieces are already regarded as visited.

Find the minimum number of moves required to achieve the objective.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq M \leq 10^5

-10^5 \leq X_i \leq 10^5

X_1, X_2, ..., X_M are all different.

Input

Input is given from Standard Input in the following format:

N M
X_1 X_2 ... X_M

Output

Find the minimum number of moves required to achieve the objective.

Sample Input 1

2 5
10 12 1 2 14

Sample Output 1

5

The objective can be achieved in five moves as follows, and this is the minimum number of moves required.

Initially, put the two pieces at coordinates 1 and 10.

Move the piece at coordinate 1 to 2.

Move the piece at coordinate 10 to 11.

Move the piece at coordinate 11 to 12.

Move the piece at coordinate 12 to 13.

Move the piece at coordinate 13 to 14.

Sample Input 2

3 7
-10 -3 0 9 -100 2 17

Sample Output 2

19

Sample Input 3

100 1
-100000

Sample Output 3

0



Sample input:
2 5
10 12 1 2 14


Sample output:
5

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
Xs = list(mapint())
Xs.sort()
dist = []
for i in range(1, M):
    dist.append(Xs[i]-Xs[i-1])
dist.sort()
print(sum(dist[:M-N]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
Y = []
for i in range(M-1):
    Y.append(X[i+1]-X[i])
Y.sort()
print(sum(Y[:M-N]))

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
X = list(map(int,input().split()))

ans = sorted([X[x+1] - X[x] for x in range(M-1)])

if N >= M:
    print(0)
else:
    print(sum(ans[:M-N]))

Submission status: Wrong Answer

Solution code:
N,M,*X = map(int, open(0).read().split())
X.sort()
D = [abs(X[i+1] - X[i]) for i in range(M-1)]
if N >= M:
    print(0)
else:
    print(X[-1] - X[0] - sum(sorted(D)[-(N-1):][::-1]))

Submission status: Wrong Answer

Solution code:
N,M,*X = map(int, open(0).read().split())
X.sort()
D = [abs(X[i+1] - X[i]) for i in range(M-1)]
if N >= M:
    print(X[-1] - X[0] - sum(sorted(D)[-(N-1):][::-1]))
else:
    print(0)

Submission status: Wrong Answer

Solution code:
import sys

# N: コマ数
# M: 地点数

N,M,*X = map(int, open(0).read().split())

# コマ数が地点数以上の場合、各地点にコマを配置できる
# よって 0 回の移動で目的を達成できる
if N >= M:
    print(0)
    sys.exit()

X.sort()
D = sorted(abs(X[i+1] - X[i]) for i in range(M-1))
print(X[-1] - X[0] - sum(D[-(N-1):]))

Submission status: Wrong Answer

Solution code:
import sys
 
# N: コマ数
# M: 地点数
 
N,M,*X = map(int, open(0).read().split())
 
# コマ数が地点数以上の場合、各地点にコマを配置できる
# よって 0 回の移動で目的を達成できる
if N >= M:
    print(0)
    sys.exit()
 
X.sort()
ans = []
for i in range(M-1):
    ans.append(abs(X[i+1] - X[i]))
 
ans.sort()
print(X[-1] - X[0] - sum(ans[:N-1:-1]))

Submission status: Wrong Answer

Solution code:
import sys

# N: コマ数
# M: 地点数

N,M,*X = map(int, open(0).read().split())

# コマ数が地点数以上の場合、各地点にコマを配置できる
# よって 0 回の移動で目的を達成できる
if N >= M:
    print(0)
    sys.exit()

X.sort()
ans = []
for i in range(M-1):
    ans.append(abs(X[i+1] - X[i]))

ans.sort()
print(X[-1] - X[0] - sum(ans[-(N-1):]))

Submission status: Wrong Answer

Solution code:
import sys

# N: コマ数
# M: 地点数

N,M,*X = map(int, open(0).read().split())

# コマ数が地点数以上の場合、各地点にコマを配置できる
# よって 0 回の移動で目的を達成できる
if N >= M:
    print(0)
    sys.exit()

X.sort()

ans = []
for i in range(M-1):
    ans.append(abs(X[i+1] - X[i]))

ans.sort()
print(sum(ans[:-(N-1)]))

Submission status: Wrong Answer

Solution code:
import sys

# N: コマ数
# M: 地点数

N,M,*X = map(int, open(0).read().split())

# コマ数が地点数以上の場合、各地点にコマを配置できる
# よって 0 回の移動で目的を達成できる
if N >= M:
    print(0)
    sys.exit()

X.sort()

ans = []
for i in range(1, len(X)):
    ans.append(abs(X[i] - X[i - 1]))

ans.sort()
print(sum(ans[:-(N-1)]))

Submission status: Wrong Answer

Solution code:
import sys

# N: コマ数
# M: 地点数

N,M,*X = map(int, open(0).read().split())

# コマ数が地点数以上の場合、各地点にコマを配置できる
# よって 0 回の移動で目的を達成できる
if N >= M:
    print(0)
    sys.exit()

X.sort()

ans = []
for i in range(len(X)-1):
    ans.append(abs(X[i+1] - X[i]))

ans.sort()
print(sum(ans[:-(N-1)]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
X = sorted(map(int,input().split()))
D = sorted(x2-x1 for x1,x2 in zip(X,X[1:]))
print(sum(D[:N-1]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
dx = [0] * (m - 1)
for i in range(m - 1):
    dx[i] = x[i + 1] - x[i]
dx.sort()
print(sum(dx[:m-n]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
y=[]
for i in range(len(x)-1):
  y+=[x[i+1]-x[i]]
y.sort()
print(sum(y[:m-n]))

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc117/tasks/abc117_c

import numpy as np

N, M = list(map(int, input().split()))
Xs = list(map(int, input().split()))
x = np.array(sorted(Xs))
print(np.sum(np.sort(np.diff(x))[:-N+1]))

Submission status: Wrong Answer

Solution code:
# abc117_c.py
# https://atcoder.jp/contests/abc117/tasks/abc117_c

# C - Streamline /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 数直線と N個のコマを用いて 1人でゲームを行います。
# はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
# このとき、同じ座標に複数のコマを置いても構いません。
# 以下の移動を繰り返して、座標 X1,X2,...,XMの M個の地点全てをいずれかのコマで訪れることが目的です。
# 移動: コマを 1つ選び、そのコマの座標を x とする。そのコマを座標 x+1 もしくは座標 x−1に移動する。
# ただし、最初にコマを置いた座標はその時点で訪れたとみなします。
# 目的を達成するまでに移動を行う回数の最小値を求めてください。

# 制約
#     入力はすべて整数である。
#     1≤N≤105
#     1≤M≤105
#     −105≤Xi≤105
#     X1,X2,...,XMは全て異なる。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N M
# X1 X2 ... XM

# 出力
# 目的を達成するまでに移動を行う回数の最小値を出力せよ。

# 入力例 1
# 2 5
# 10 12 1 2 14

# 出力例 1
# 5

# 以下の手順で 5回移動を行うと目的を達成でき、このときが最小です。
#     はじめに 2個のコマをそれぞれ座標 1, 座標 10に置きます。
#     座標 1のコマを座標 2に移動します。
#     座標 10のコマを座標 11に移動します。
#     座標 11のコマを座標 12に移動します。
#     座標 12のコマを座標 13に移動します。
#     座標 13のコマを座標 14に移動します。

# 入力例 2
# 3 7
# -10 -3 0 9 -100 2 17

# 出力例 2
# 19

# 入力例 3
# 100 1
# -100000

# 出力例 3
# 0


def calculation(lines):
    # line = lines[0]
    # N = int(lines[0])
    N, M = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i+1]))

    if N >= M:
        return [0]

    values.sort()
    print(values)

    difs = list()
    for i in range(len(values)-1):
        difs.append(values[i+1] - values[i])

    difs.sort()
    print(difs)

    result = 0
    for i in range(M-N):
        result += difs[i]

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 5', '10 12 1 2 14']
        lines_export = [5]
    if pattern == 2:
        lines_input = ['3 7', '-10 -3 0 9 -100 2 17']
        lines_export = [19]
    if pattern == 3:
        lines_input = ['100 1', '-100000']
        lines_export = [0]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# abc117_c.py
# https://atcoder.jp/contests/abc117/tasks/abc117_c

# C - Streamline /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 数直線と N個のコマを用いて 1人でゲームを行います。
# はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
# このとき、同じ座標に複数のコマを置いても構いません。
# 以下の移動を繰り返して、座標 X1,X2,...,XMの M個の地点全てをいずれかのコマで訪れることが目的です。
# 移動: コマを 1つ選び、そのコマの座標を x とする。そのコマを座標 x+1 もしくは座標 x−1に移動する。
# ただし、最初にコマを置いた座標はその時点で訪れたとみなします。
# 目的を達成するまでに移動を行う回数の最小値を求めてください。

# 制約
#     入力はすべて整数である。
#     1≤N≤105
#     1≤M≤105
#     −105≤Xi≤105
#     X1,X2,...,XMは全て異なる。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# N M
# X1 X2 ... XM

# 出力
# 目的を達成するまでに移動を行う回数の最小値を出力せよ。

# 入力例 1
# 2 5
# 10 12 1 2 14

# 出力例 1
# 5

# 以下の手順で 5回移動を行うと目的を達成でき、このときが最小です。
#     はじめに 2個のコマをそれぞれ座標 1, 座標 10に置きます。
#     座標 1のコマを座標 2に移動します。
#     座標 10のコマを座標 11に移動します。
#     座標 11のコマを座標 12に移動します。
#     座標 12のコマを座標 13に移動します。
#     座標 13のコマを座標 14に移動します。

# 入力例 2
# 3 7
# -10 -3 0 9 -100 2 17

# 出力例 2
# 19

# 入力例 3
# 100 1
# -100000

# 出力例 3
# 0


def calculation(lines):
    # line = lines[0]
    # N = int(lines[0])
    N, M = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i+1]))

    if N >= M:
        return [0]

    values.sort()
    print(values)

    difs = list()
    for i in range(len(values)-1):
        difs.append(values[i+1] - values[i])

    difs.sort()
    print(difs)

    result = 0
    for i in range(M-N):
        result += difs[i]

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 5', '10 12 1 2 14']
        lines_export = [5]
    if pattern == 2:
        lines_input = ['3 7', '-10 -3 0 9 -100 2 17']
        lines_export = [19]
    if pattern == 3:
        lines_input = ['100 1', '-100000']
        lines_export = [0]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    if len(args) == 1:
        mode = 0
    else:
        mode = int(args[1])
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    if mode > 0:
        print(f'lines_input=[{lines_input}]')
        print(f'lines_export=[{lines_export}]')
        print(f'lines_result=[{lines_result}]')
        if lines_result == lines_export:
            print('OK')
        else:
            print('NG')
    finished = time.time()
    duration = finished - started
    print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
n, m, *x = map(int, open(0).read().split())
x.sort()
d = sorted(x[i] - x[i - 1] for i in range(1, m))
print(sum(d[:m - n]))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

# list X をソート O(Mlog(M)) して、目的地 X の左右の外側から順に駒を置いていく
# 残った目的地に対して、一番内側にある2つの駒を何回移動させれば良いか計算するO(M)
N, M = map(int, readline().split())

if N >= M:
    print(0)
    sys.exit()

X = list(map(int, readline().split()))
X.sort()

left = X[0]
right = X[-1]

for i in range(N):
    if i % 2 == 0:
        left = X[i//2]
    else:
        right = X[-(i//2) - 1]


count = 0
for m in range(M):
    if left < X[m] < right:
        ldis = X[m] - left
        rdis = right - X[m]

        if ldis < rdis:
            count += ldis
            left = X[m]
        else:
            count += rdis
            right = X[m]

print(count)

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10**9)
input = sys.stdin.readline

def ii(): return int(input())
def mi(): return map(int, input().split())
def lmi(): return list(map(int, input().split()))
def iif(n): return [int(input()) for _ in range(n)]
def lmif(n): return [list(map(int, input().split())) for _ in range(n)]
def ss(): return input().split()

def main():
    mod = 1000000007
    
    N, M = mi()
    if N >= M:
        print(0)
        return

    X = lmi()
    X.sort()

    X_dis = []
    for i in range(len(X) - 1):
        X_dis.append(X[i+1] - X[i])
    X_dis.sort()

    print(sum(X_dis[:-N + 1]))

    return

main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))


x.sort()
diff = []
f = x[0]
if m <= n:
    print(0)
else:
    for i in x[1:]:
        diff.append(i-f)
        f = i

    diff.sort()
    print(sum(diff[:-n+1]))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))


x.sort()
diff = []
f = x[0]
if m == 1:
    print(0)
else:
    for i in x[1:]:
        diff.append(i-f)
        f = i

    diff.sort()
    max_d = {}
    if n == 1:
        print(sum(diff))
    else:
        for i in diff[-n+1:]:
            max_d[i] = False
        ans = 0
        for i in diff:
            if i in max_d:
                if not max_d[i]:
                    max_d[i] = True
                else:
                    ans += i
            else:
                ans += i
        print(ans)

Submission status: Wrong Answer

Solution code:
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []


if M <= N:
    print(0)
    sys.exit()


    
for i in range(M-1):
    ans = abs(X[i+1] - X[i])
    anslis.append(ans)
    ans = 0

anslis = sorted(anslis)

if N==1:
    print(sum(anslis))
else:
    print(sum(anslis[0:N+1]))

Submission status: Wrong Answer

Solution code:
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []


if M <= N:
    print(0)
    sys.exit()


    
for i in range(M-1):
    ans = (X[i+1] - X[i])
    anslis.append(ans)

anslis = sorted(anslis)

print(sum(anslis[:-(N-1)]))

Submission status: Wrong Answer

Solution code:
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []


if M <= N:
    print(0)
    sys.exit()


    
for i in range(M-1):
    ans = abs(X[i+1] - X[i])
    anslis.append(ans)
    ans = 0

anslis = sorted(anslis)

print(sum(anslis[0:N+1]))

Submission status: Wrong Answer

Solution code:
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []


if M <= N:
    print(0)
    sys.exit()


    
for i in range(M-1):
    ans = (X[i+1] - X[i])
    anslis.append(ans)

anslis = sorted(anslis)

print(sum(anslis[0:N-1]))

Submission status: Wrong Answer

Solution code:
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []


if M <= N:
    print(0)
    sys.exit()


    
for i in range(M-1):
    ans = abs(X[i+1] - X[i])
    anslis.append(ans)
    ans = 0

anslis = sorted(anslis)

print(sum(anslis[0:N-1]))

Submission status: Wrong Answer

Solution code:
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []


if M >= N:
    print(0)
    sys.exit()


    
for i in range(M-1):
    ans = abs(X[i+1] - X[i])
    anslis.append(ans)
    ans = 0

anslis = sorted(anslis)

print(sum(anslis[0:N+1]))

Submission status: Wrong Answer

Solution code:
import sys 
N, M = map(int, input().split())
X = list(map(int, input().split()))

X = sorted(X)

anslis = []
        
    
for i in range(M-1):
    ans = abs(X[i+1] - X[i])
    anslis.append(ans)
    ans = 0

anslis = sorted(anslis)

print(sum(anslis[0:N+1]))

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
x = sorted(list(map(int, input().split())))

nums = [0]*(m-1)
for i in range(m-1): nums[i] = x[i+1] - x[i]
nums = sorted(nums)
print(sum(nums[:m-1-(n-1)]))

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    X = sorted(il())

    b, f = [], []
    for n in range(M-1):
        b.append(abs(X[n] - X[n+1]))
    X = X[::-1]
    for n in range(M-1):
        f.append(abs(X[n] - X[n+1]))
    print(min(sum(sorted(b)[:M-N]), sum(sorted(f)[:M-N])))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    X = sorted(il())

    cnt = []
    for n in range(M-1):
        cnt.append(abs(X[n] - X[n+1]))
    print(sum(sorted(cnt)[:M-N]))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M = (int(X) for X in input().split())
if N>=M:
    print(0)
else:
    P   = sorted(int(X) for X in input().split())
    Mov = sorted(P[X+1]-P[X] for X in range(0,M-1))
    print(sum(Mov[:1-N]))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def main():
    input = sys.stdin.readline
    n,m = map(int, input().split())
    x_list = list(map(int, input().split()))
    if m == 1:
        print(0)
        exit(0)
    sabun_list = []
    x_list.sort()
    for i,x in  enumerate(x_list):
        if i == 0:
            continue
        sabun_list.append(x - x_list[i-1])
    result = 0
    max_sabun_index_list = []
    #一個は左端確定
    max_sabun_index_list.append(0)
    for i in range(n-1):
        max_index = sabun_list.index(max(sabun_list))
        max_sabun_index_list.append(max_index + 1)
        sabun_list[max_index] = -1
    
    max_sabun_index_list.sort()
    #最後以外
    for i in range(len(max_sabun_index_list) - 1):
        result += x_list[max_sabun_index_list[i+1]-1] - x_list[max_sabun_index_list[i]]
    #最後
    result += x_list[-1] - x_list[max_sabun_index_list[-1]]

    print(result)

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
X = list(map(int,input().split()))
if len(X)<2:
    print(0)
else:    
    X.sort()

    diffs = []
    for i in range(M-1):
        diffs.append(abs(X[i+1]-X[i]))
    diffs.sort(reverse=True)
    print(X[M-1]-X[0]-sum(diffs[:N]))

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    Xs = [int(item) for item in input().split()]
    if N < M:
        Xs.sort()
        ds = [Xs[i] - Xs[i-1] for i in range(1, M)]
        ds.sort()
        # print(ds)
        print(sum(ds[:-N+1]))

    else:
        print(0)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    Xs = [int(item) for item in input().split()]
    if N < M-1:
        Xs.sort()
        ds = [Xs[i] - Xs[i-1] for i in range(1, M)]
        ds.sort()
        # print(ds)
        print(sum(ds[:-1*(N-1)]))
    elif N == 1:
        Xs.sort()
        print(Xs[-1] - Xs[0])
        
    else:
        print(0)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
def resolve():
    '''
    code here
    '''
    import collections
    N, M = [int(item) for item in input().split()]
    Xs = [int(item) for item in input().split()]
    if N < M:
        Xs.sort()
        ds = [Xs[i] - Xs[i-1] for i in range(1, M)]
        ds.sort()
        # print(ds)
        print(sum(ds[:-1*(N-1)]))
    else:
        print(0)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
X = sorted(list(map(int,input().split())))
Xsub = []
for i in range(M-1):
    Xsub.append(X[i+1]-X[i])
    
Xsub = sorted(Xsub)
print(sum(Xsub[:-(N-1)]))

Submission status: Wrong Answer

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = il()
    X = sorted(il())

    diff = []
    for n in range(M - 1):
        diff.append(abs(X[n] - X[n + 1]))
    omit = sorted(diff, reverse=True)
    omit = set(omit[:N - 1])

    ret, cnt = 0, N - 1
    for d in diff:
        if cnt != 0 and d in omit:
            cnt -= 1
            continue
        else:
            ret += d
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import heapq
n,m = map(int, raw_input().split(' '))

# I am given n pieces

xis = map(int, raw_input().split())
xis.sort()
heap = []
seen = set([])
for u,v in zip(xis,xis[1:]):
	heapq.heappush(heap,(-(v-u), u,v))

def f(heap,n,m):
	
	if n >= m:
		return 0
	if n == 1:
		return  -sum([a for a,b,c in heap] or [0])
	nn = n

	while(heap and n >= 2):
		d,u,v = heapq.heappop(heap)
		if u not in seen:
			seen.add(u)
			n-=1
		if v not in seen:
			seen.add(v)
			n-=1
	s = 0
	while(heap):
		d,u,v = heapq.heappop(heap)
		if (u in seen) and (v in seen):
			s += 0
		else:
			if n > 0 and len(seen):
				n -=1
				seen.add(u)
			else:
				s += -d
	#print xis, nn, 'points', seen
	return s

print f(heap,n,m)

Submission status: Wrong Answer

Solution code:
import heapq
n,m = map(int, raw_input().split(' '))

# I am given n pieces

xis = map(int, raw_input().split())
xis.sort()
heap = []
seen = set([])
for u,v in zip(xis,xis[1:]):
	heapq.heappush(heap,(-(v-u), u,v))

def f(heap,n,m):
	
	if n >= m:
		return 0
	if n == 1:
		return  -sum([a for a,b,c in heap] or [0])


	while(heap and n >= 2):
		d,u,v = heapq.heappop(heap)
		if u not in seen:
			seen.add(u)
			n-=1
		if v not in seen:
			seen.add(v)
			n-=1

	s = -sum([a for a,b,c in heap] or [0])
	if n and s:
		for d,u,v in heap:
			s -= -d
			n-=1
			break

	if n:
		for d,u,v in heap:
			if u in seen or v in seen:
				s -= -d
				n-=1
				break
	return s

print f(heap,n,m)

Submission status: Wrong Answer

Solution code:
import heapq
n,m = map(int, raw_input().split(' '))

# I am given n pieces

xis = map(int, raw_input().split())
xis.sort()
heap = []
seen = set([])
for u,v in zip(xis,xis[1:]):
	heapq.heappush(heap,(-(v-u), u,v))

def f(heap,n):
	if n == 1:
		return  -sum([a for a,b,c in heap] or [0])


	while(heap and n >= 2):
		d,u,v = heapq.heappop(heap)
		if u not in seen:
			seen.add(u)
			n-=1
		if v not in seen:
			seen.add(v)
			n-=1

	s = -sum([a for a,b,c in heap] or [0])
	if n and s:
		for d,u,v in heap:
			s -= -d
			n-=1
			break

	if n:
		for d,u,v in heap:
			if u in seen or v in seen:
				s -= -d
				n-=1
				break
	return s

print f(heap,n)

Submission status: Wrong Answer

Solution code:
import heapq
n,m = map(int, raw_input().split(' '))

# I am given n pieces

xis = map(int, raw_input().split())
xis.sort()
heap = []
seen = set([])
for u,v in zip(xis,xis[1:]):
	heapq.heappush(heap,(-(v-u), u,v))
	
while(heap and n >= 2):
	d,u,v = heapq.heappop(heap)
	if u not in seen:
		seen.add(u)
		n-=1
	if v not in seen:
		seen.add(v)
		n-=1

s = -sum([a for a,b,c in heap] or [0])
if n and s:
	for d,u,v in heap:
		s -= -d
		n-=1
		break

if n:
	for d,u,v in heap:
		if u in seen or v in seen:
			s -= -d
			n-=1
			break
print s

Submission status: Wrong Answer

Solution code:
import heapq
n,m = map(int, raw_input().split(' '))

# I am given n pieces

xis = map(int, raw_input().split())
xis.sort()
heap = []
seen = set([])
for u,v in zip(xis,xis[1:]):
	heapq.heappush(heap,(-(v-u), u,v))
	seen.add(u)
	seen.add(v)
while(heap and n >= 2):
	n -= 2
	heapq.heappop(heap)
s = -sum([a for a,b,c in heap] or [0])
if n:
	for d,u,v in heap:
		if u in seen or v in seen:
			s -= -d
			break

print s

Submission status: Wrong Answer

Solution code:
# 初期入力
import sys
input = sys.stdin.readline
N,M = (int(i) for i in input().split())
X = list(map(int, input().split()))
if N >=M:
    ans =0
else:
    X.sort()
    dif =[10**6]*(M-1)
    for i in range(M-1):
        dif[i] =X[i+1] -X[i]
    dif.sort()
    ans =dif[:-(N-1)]
    ans =sum(ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()

ruisekisa = [0]*(M-1)
for i in range(0,M-1,1):
    ruisekisa[i]=X[i+1]-X[i]

ruisekisa.sort()
print(sum(ruisekisa[0:M-N]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()

ruisekisa = [0]*(M-1)
for i in range(0,M-1,1):
    ruisekisa[i]=X[i+1]-X[i]

ruisekisa.sort()
print(sum(ruisekisa[0:M-1-N+1]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())

lc = list(map(int,input().split()))
lc.sort()
#print(lc)
diff = []
for i in range(M-1):
    diff.append(lc[i+1]-lc[i])
    
#print(diff)
diff.sort()
diff_min = diff[:M-N]
print(sum(diff_min))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
a=[]
for i in range(m-1):
    a.append(abs(x[i+1]-x[i]))
a.sort()
al=x[-1]-x[0]
a_skip=sum(a[-n+1:])
print(al-a_skip)

Submission status: Wrong Answer

Solution code:
import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
(N,M) = map(int, input().split())
X = map(int, input().split())
X = sorted(X)

Y = []
for i in range(1,M):
    Y.append((i,X[i] - X[i-1]))

Y = sorted(Y, key=lambda x: (x[1]))
Y.reverse()

Z = []
last = 0
for i in range(0,min(N-1, len(Y))):
    if last < Y[i][0]:
        Z.append(X[last:Y[i][0]])
        last = Y[i][0]
Z.append(X[last:])
if len(Z) == 0:
    Z.append(X)

s = 0
for array in Z:
    if len(array) > 0:
        u = max(array)
        l = min(array)
        s += u - l

print(s)

Submission status: Wrong Answer

Solution code:
import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
(N,M) = map(int, input().split())
X = map(int, input().split())
X = sorted(X)

Y = []
for i in range(1,M):
    Y.append((i,X[i] - X[i-1]))

Y = sorted(Y, key=lambda x: (x[1]))
Y.reverse()

Z = []
last = 0
for i in range(0,min(N-1, len(Y))):
    print((last, Y[i][0]))
    if last < Y[i][0]:
        Z.append(X[last:Y[i][0]])
        last = Y[i][0]
Z.append(X[last:])
if len(Z) == 0:
    Z.append(X)

s = 0
for array in Z:
    if len(array) > 0:
        u = max(array)
        l = min(array)
        s += u - l

print(s)

Submission status: Wrong Answer

Solution code:
import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
(N,M) = map(int, input().split())
X = map(int, input().split())
X = sorted(X)

Y = []
for i in range(1,M):
    Y.append((i,X[i] - X[i-1]))

Y = sorted(Y, key=lambda x: (x[1]))
Y.reverse()

Z = []
last = 0
for i in range(0,min(N-1, len(Y))):
    Z.append(X[last:Y[i][0]])
    last = Y[i][0]
Z.append(X[last:])
if len(Z) == 0:
    Z.append(X)

s = 0
for array in Z:
    if len(array) > 0:
        u = max(array)
        l = min(array)
        s += u - l

print(s)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
*X,=map(int,input().split())
X.sort()

count=[0]*(M-1)
i=1
while i<M:
    count[i-1]=X[i]-X[i-1]
    i+=1
count.sort()

print(sum(count[:M-N]))

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()

if n>=m:
    print(0)
    quit()

ans=[]
for i in range(m-1):
    ans.append(x[i+1]-x[i])
# print(ans)

ans.sort()
print(sum(ans[:-n+1]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
Y = []
if N>=M:
    print(0)
else:
    for i in range(M-1):
        Y.append(X[i+1]-X[i])
    Y.sort()
    print(sum(Y[:-(N-1)]))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
Y = []
for i in range(M-1):
    Y.append(X[i+1]-X[i])
Y.sort()
print(sum(Y[:-(N-1)]))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
b=[]
for i in range(m-1):
  b.append(a[i+1]-a[i])
b=sorted(b)
print(sum(b[:m-n+1]))