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: Accepted

Solution code:

def solve():
    if N >= M:
        return 0
    elif N == 1:
        cnt = abs(X[-1] - X[0])
        return cnt
    L = [0] * (M-1)
    
    for i in range(len(L)):
        L[i] = X[i+1] - X[i]
    L.sort()
    return sum(L[:M-N])



if __name__=="__main__":
    N,M = list(map(int, input().split()))
    X = list(map(int, input().split()))
    X.sort()
    print(solve())

Submission status: Accepted

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]))
    diff = sorted(diff, reverse=True)
    ret = sum(diff[N-1:])
    print(ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

n,m=map(int,input().split())
if n>=m:
    print(0)
    exit()

lst=sorted(map(int,input().split()))
sa=[]
for i in range(m-1):
    sa.append(lst[i+1]-lst[i])
sa=sorted(sa)
print(sum(sa[:m-n]))

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools

def solve():
    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    x.sort()
    if n >= m:
        print(0)
    else:
        diff = [abs(x[i] - x[i+1]) for i in range(m-1)]
        diff.sort(reverse=True)
        ans = sum(diff)
        for i in range(n-1):
            ans -= diff[i]
        print(ans)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

xis = map(int, raw_input().split())
xis.sort()
distances = [v- u for u,v in zip(xis,xis[1:])]
distances.sort(key = lambda x:-x)
print sum(distances[n-1:] or [0])

Submission status: Accepted

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

# I am given n pieces
if n >= m:
	print 0
else:
	xis = map(int, raw_input().split())
	xis.sort()


	distances = [v- u for u,v in zip(xis,xis[1:])]
	distances.sort(key = lambda x:-x)
	print sum(distances[n-1:] or [0])

Submission status: Accepted

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 =[-1]*(M-1)
    for i in range(M-1):
        dif[i] =X[i+1] -X[i]
    dif.sort()
    ans =dif[:M-N]
    ans =sum(ans)
print(ans)

Submission status: Accepted

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:max(M-N,0)]))#負方向のout index が変な挙動するのよ

Submission status: Accepted

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

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

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: Accepted

Solution code:
import sys
N,M = map(int,input().split())
if N >= M:
    print(0)
    sys.exit()
    
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: Accepted

Solution code:
N,M=map(int,input().split())
R=[0]*(M-1)
L=list(map(int,input().split()))
L=sorted(L)
for i in range(M-1):
  R[i]=abs(L[i+1]-L[i])
c=max(L)-min(L)
R=sorted(R,reverse=True)
print(c-sum(R[:min(N-1,len(R))]))

Submission status: Accepted

Solution code:
n, m, *xx = map(int, open(0).read().split())

xx.sort()

diff = [a - b for a, b in zip(xx[1:], xx[:-1])]

diff.sort(reverse=True)

print(sum(diff[n-1:]))

Submission status: Accepted

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=sum(a)
if n==1:
    print(al)
else:
    a_skip=sum(a[-n+1:])
    print(al-a_skip)

Submission status: Accepted

Solution code:
import sys

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())


def main():
    N, M = mi()
    X = list(mi())
    X.sort()
    if N >= M:
        print(0)
        return
    dif = [(X[i+1]-X[i], i) for i in range(M-1)]
    dif.sort(reverse=True)
    koma = [-1]+[dif[i][1] for i in range(N-1)]+[M-1]
    print(sum(X[koma[i+1]]-X[koma[i]+1] for i in range(N)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
x = sorted(LIST())
dx = [x[i+1]-x[i] for i in range(m-1)]
dx.sort(reverse=True)

if n >= m:
    print(0)
else:
    print(x[m-1]-x[0]-sum(dx[0:n-1]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = sorted(list(map(int, input().split())))
if n >= m:
  print(0)
  exit()
diff = sorted([lst[i + 1] - lst[i] for i in range(m - 1)], reverse=True)
print(sum(diff[n - 1:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
X = sorted(list(map(int, input().split())))
if n >= m : print(0)
else:
    d = sorted([i-j for i, j in zip(X[1:], X)])
    print(sum(d[:m-n]))

Submission status: Accepted

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()

I = list(map(lambda x: x[0], Y[0:min(N-1, len(Y))]))
I.sort()

Z = []
last = 0
for i in range(0,min(N-1, len(Y))):
    if last < I[i]:
        Z.append(X[last:I[i]])
        last = I[i]
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: Accepted

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

if N >= M:
    print(0)
else:
    D = []
    for i in range(len(X)-1):
        D.append(abs(X[i]-X[i+1]))
    D = list(sorted(D))
    print(sum(D[:M-N]))

Submission status: Accepted

Solution code:
import itertools
n,m=map(int, input().split())
x=[int(i) for i in input().split()]
x.sort()
if(n>=m):
    print(0)
    exit()
dist = abs(x[-1]-x[0])

diff = []

for i in range(m-1):
    diff.append([abs(x[i]-x[i+1]),i])

diff.sort(key = lambda x:x[0],reverse = True)
for i in range(n-1):
    dist-=diff[i][0]
print(dist)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():

    N, M = in_nn()
    X = sorted(in_nl())

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

    X_diff.sort(reverse=True)
    # print(X_diff)
    # print(X)
    N = min(N, M)
    ans = X[-1] - X[0] - sum(X_diff[:N - 1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#ABC117-C
n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
sabun = []
for i in range(1,m):
    sabun.append(x[i]-x[i-1])
sabun.sort(reverse=True)

print(sum(sabun[n-1:]))

Submission status: Accepted

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

# 地点間の距離をdiffに記憶
for i in range(M - 1):
    diff.append(abs(X[i] - X[i + 1]))

# N個の区間でM個の地点を覆う
# すると、N-1個の覆われていない区間ができる
# これを最大にすると覆う区間を最小にできる

diff = sorted(diff, reverse=True)
#print(diff)
# diffの中で大きい順にN-1個の総和をとる
#数直線の長さ - 覆わなくて良い範囲の総和
ans = (X[-1] - X[0]) - sum(diff[:N - 1])
# ans = sum(diff[:N-1]) でもOK、どうしても覆う必要がある区間の和
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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[:max(M-N,0)]))

Submission status: Accepted

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

if N >= M:
    print(0)

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

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N, M = I()
X = l()
X.sort()
kyori = []

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

if M == 1:
    print(0)
    sys.exit()
for i in range(len(X)-1):
    s = X[i+1]-X[i]
    kyori.append(s)

kyori.sort()
kyori.reverse()

for j in range(N-1):
    kyori.pop(0)

print(sum(kyori))

Submission status: Accepted

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

diff = sorted(diff, reverse=True)

dist = x[-1] - x[0]
if dist < n:
    print(0)
    exit()

if m < n:
    print(0)
    exit()

for i in range(n-1):
    dist -= diff[i]

print(dist)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
if n >= m:
    print(0)
else:
    x = [int(i) for i in input().split()]
    x.sort()
    d = x[- 1] - x[0]
    y = []
    for i in range(m - 1):
        y.append(x[i + 1] - x[i])
    y.sort(reverse=True)
    for i in range(n - 1):
        d -= y[i]
    print(d)

Submission status: Accepted

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

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

sa = []

for i in range(1, m):
    sa.append(abs(X[i] - X[i - 1]))

sa.sort(reverse=True)
# print(sa)
# print((max(X) - min(X)))
print((max(X) - min(X)) - sum(sa[:n-1]))

Submission status: Accepted

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(ans)
for i in range(n-1):
    ans[-1-i]=0
print(sum(ans))

Submission status: Accepted

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

Submission status: Accepted

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=sorted(Y)[::-1]
    print(sum(Y[N-1:]))

Submission status: Accepted

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)[::-1]
print(sum(b[n-1:]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
if n>=m:
  print(0)
  import sys
  sys.exit()
x=list(map(int,input().split()))
x.sort()
l=[]
for i in range(m-1):
  l.append(x[i+1]-x[i])
l.sort()
sm=0
for j in range(m-n):
  sm+=l[j]
print(sm)

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
d=[0]*m
for i in range(1,m):
  d[i]=a[i]-a[i-1]
d.sort(reverse=True)
print(sum(d[n-1:]))

Submission status: Accepted

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

Submission status: Accepted

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

d = [0] * (M - 1)

if (N >= M):
    print(0)
    exit()
else:
    for i in range(M):
        if (i == M - 1):
            break
        else:
            d[i] = X[i + 1] - X[i]

d.sort(reverse=True)
count = 0
for i in d:
    if (N > 1):
        N -= 1
        continue
    elif(N == 1):
        count += i

print(count)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    X = [j for j in map(int, input().split())]
    if N >= M:
        print(0)
        exit()
    X.sort()
    s = max(X)-min(X)
    d = [X[i+1]-X[i] for i in range(M-1)]
    d.sort()
    if N == 1:
        print(s)
    else:
        print(s-sum(d[-N+1:]))


main()

Submission status: Accepted

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

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

x = sorted(x)
diff = [0 for _ in range(m-1)]
for i in range(m-1):
    diff[i] = x[i+1] - x[i]

diff = sorted(diff, reverse=True)
ans = sum(diff[n-1:])
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split(" "))
xList = [int(i) for i in input().split(" ")]
xList = sorted(xList)
dList = [0]
for i in range(len(xList) -1) :
    dList.append(xList[i+1] - xList[i])
dList = sorted(dList, reverse=True)    

for i in range(n-1) :
    dList[i] = 0
    if(i == len(dList) -1) :
        break
print(sum(dList))

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
X = list(map(int, input().split()))
X_sort = np.array(sorted(X))

diff_arr = X_sort[1:] - X_sort[:M-1]
print(sum(sorted(diff_arr, reverse = True)[N-1:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
apple = list(map(int, input().split()))
orange = []
count = 0
if n >= m:
    count = 1
else:
    apple = sorted(apple)
    for i in range(m-1):
        orange.append(apple[i+1] - apple[i])
orange = sorted(orange)

if count == 0:
    if len(orange) != 1:
        if n != 1:
            print(sum(orange[:-(n-1)]))
        else:
            print(sum(orange))
    else:
        print(orange[0])
else:
    print(0)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
if m == 1:
    print(0)
else:
    u = [0] * (100000)
    for i in range(m-1):
        u[i] = x[i+1]-x[i]
    u.sort(reverse=True)
    c = 0
    for i in range(n-1):
        c += u[i]
    print(sum(u)-c)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
if m == 1:
    print(0)
else:
    u = [0] * (100010)
    for i in range(m-1):
        u[i] = x[i+1]-x[i]
    u.sort(reverse=True)
    c = 0
    for i in range(n-1):
        c += u[i]
    print(sum(u)-c)

Submission status: Accepted

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

ans=0
if n>=m:
    ans=0
else:
    x.sort()
    diff=[0]*(m-1)

    for i in range(m-1):
        diff[i]=x[i+1]-x[i]

    diff.sort()

    ans=0
    
    for i in range(m-n):
        ans+=diff[i]

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    xs = list(map(int, input().split()))
    if n >= m:
        print(0)
        exit()
    xs = sorted(xs)
    diff_xs = sorted([xs[i+1] - xs[i] for i in range(m-1)])
    ans = sum(diff_xs[:m-n])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
X = list(map(int, input().split()))
 
ans = 0
if n < m:
    X.sort()
    L = sorted([X[i + 1] - X[i] for i in range(m - 1)], reverse=True)
    ans = sum(L[n - 1: ])
 
print(ans)

Submission status: Accepted

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

x = list(map(int,input().split()))

dist = []
x.sort()
if M < N:
    print(0)
    exit()
for i in range(M-1):
    dist.append(abs(x[i+1]-x[i]))

dist.sort()

for i in range(N-1):
    dist.pop()
 
print(sum(dist))

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
n = min(n,m)
x = sorted(map(int,input().split()))
dx = [0] * (m-1)

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

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
x = sorted(map(int, input().split()))

if N >= M:
    print(0)
    sys.exit()
diff = [0]*(M-1)
for i in range(M-1):
    diff[i] = x[i+1] - x[i]
diff.sort()
ans = sum(diff[:M-N])
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    X = sorted(map(int, input().split()))
    if N >= M:
        print(0)
        return
    D = [0]*(M-1)
    for i in range(M-1):
        D[i] = X[i + 1] - X[i]
    D.sort()
    ans = sum(D[:M-N])
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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()
if M<=N:
  print(0)
else:
  print(sum(Y[:M-N]))

Submission status: Accepted

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

if n>=m:
    print(0)
    sys.exit()

def quicksort(a, left: int, right: int):
    #a[left]〜a[right]をクイックソート
    pl=left
    pr=right
    pivot= a[(left +right)//2]

    #print(f'a[{left}]~a[{right}] : ', *a[left : right +1])

    while pl<=pr:
        while a[pl] <pivot: pl+=1
        while a[pr] >pivot: pr-=1
        if pl <= pr:
            a[pl], a[pr]= a[pr], a[pl]
            pl+=1
            pr-=1

    if left < pr: quicksort(a, left, pr)
    if pl < right: quicksort(a, pl, right)

def quick_sort(a):
    quicksort(a, 0, len(a)-1)

quick_sort(x)
dis_list=[0]*(m-1)
dis_sm=0
for i in range(m-1):
    dis=x[i+1]-x[i]
    dis_list[i]=dis
    dis_sm+=dis

quick_sort(dis_list)
for i in range(n-1):
    dis_sm-=dis_list[-(i+1)]

print(dis_sm)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
y = []
for s, t in zip(x, x[1:]):
    y.append(t - s)
y.sort()
if n >= m:
    print(0)
else:
    print(sum(y[:-(n-m)]))

Submission status: Accepted

Solution code:
import heapq
n,m=map(int,input().split())
x=sorted(list(map(int,input().split())))
diff=[]
heapq.heapify(diff)
if n>=m:
    print(0)
else:
    for i in range(m-1):
        heapq.heappush(diff,x[i]-x[i+1]+1)
    temp=0
    for _ in range(n-1):
        temp-=heapq.heappop(diff)
    print(x[m-1]-x[0]+1-temp-n)

Submission status: Accepted

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

Submission status: Accepted

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

if n >= m :
  print(0)
else:
  y = [0] * (m-1)
  x.sort()
  for i in range(1,m):
    y[i-1] = abs(x[i] - x[i-1])
  y.sort(reverse=True)
  print(sum(y[n-1:]))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n, m, *x = map(int, read().split())

if n >= m:
    print('0')
    exit()

x = sorted(x)
l = sorted([x[i + 1] - x[i] for i in range(m-1)])

print(sum(l[:m-n:]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
num=[]
if n>=m:
    ans=0
else:
    x.sort()
    for i in range(m-1):
        num.append(x[i+1]-x[i])
    num.sort()
    ans=sum(num[:m-n])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
if n >= m:
    print(0)
    exit()
l = [0 for _ in range(m-1)]
for i in range(m-1):
    l[i] = x[i+1] - x[i]
l.sort(reverse=True)
print(sum(l[n-1:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
if n >= m:
    print(0)
    exit()
if n == 1:
    print(max(x)-min(x))
    exit()
l = [0 for _ in range(m-1)]
for i in range(m-1):
    l[i] = x[i+1] - x[i]
l.sort(reverse=True)
print(sum(l[n-1:]))

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split())) 
X = sorted(list(map(int,input().split())))
A= []
for i in range(M-1):
    A.append(X[i+1] - X[i])
A = sorted(A,reverse = True)

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x_list = list(map(int,input().split()))
x_list.sort()
dif_list = []
for i in range(1,m):
  dif_list.append(x_list[i] - x_list[i-1])
  
dif_list.sort(reverse = True)
if n - 1 >= len(dif_list):
  print(0)
else:
  print(sum(dif_list[n-1:]))

Submission status: Accepted

Solution code:
import numpy as np
import sys
n, m = map(int, input().split())
if n >= m:
    print(0)
    sys.exit()
x = [int(i) for i in input().split()]
x = np.array(sorted(x))
diff = np.abs(np.diff(x))
diff = sorted(diff)
if n == 1:
    print(sum(diff))
else:
    print(sum(diff[:-n + 1]))

Submission status: Accepted

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

ans = 0
if n < m:
    X.sort()
    L = sorted([X[i + 1] - X[i] for i in range(m - 1)], reverse=True)
    ans = sum(L[n - 1: ])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

lis =sorted(lis)

if n > m:
    print(0)
    exit()
    
tmp = []
for i in range(m-1):
    tmp.append(lis[i+1] - lis[i])
    
tmp = sorted(tmp)

if n == 1:
    print(sum(tmp))
else:
    print(sum(tmp[:-(n-1)]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
y=[]
if n>=m:
    print(0)
    exit()
for i in range(m-1):
    y.append(x[i+1]-x[i])
z=sorted(y,reverse=True)
count=0
for i in range(n-1):
    count+=z[i]
print(x[-1]-x[0]-count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=sorted(list(map(int,input().split())))
if n>=m:
	print(0)
	exit()
x=[]
for i in range(len(X)-1):
	x.append(X[i+1]-X[i])
x.sort()
if n==1:print(sum(x))
else:print(sum(x[:-(n-1)]))

Submission status: Accepted

Solution code:
import sys
n,m = map(int,input().split())
ls = list(map(int,input().split()))
ls.sort()
if n >= m:
    print(0)
    sys.exit()
for i in range(m-1):
    ls[i] = ls[i+1]-ls[i]
del ls[-1]
ls.sort()
if n == 1:
    print(sum(ls))
else:
    ls = ls[:-(n-1)]
    print(sum(ls))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = list(map(int,input().split()))
x = sorted(x,reverse=True)
dist = []
for i in range(len(x)-1):
    dist.append(x[i]-x[i+1])
dist = sorted(dist,reverse=True)
ext = n-1
for i in range(ext):
    if not dist:
        print(0)
        exit()
    dist.pop(0)
print(sum(dist))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
y = sorted(x)
keep = []
ans = 0
for i in range(m - 1):
    keep.append(y[i + 1] - y[i])
keep = sorted(keep)
for i in range(max(0, m - n)):
    ans += keep[i]
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    x = sorted(x)
    y = []
    s = x[m - 1] - x[0]
    for i in range(1, m):
        y.append(x[i] - x[i - 1])
    y = sorted(y, reverse=True)
    m = sum(y[0: n - 1])
    print(s - m)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve(N: int, M: int, X: "List[int]"):
    if N >= M:
        return 0
    X = sorted(X)
    D = [x2 - x1 for x1, x2 in zip(X, X[1:])]
    return sum(sorted(D)[:M-N])


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    X = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    print(solve(N, M, X))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

if N >= M:
  print(0)
else:
  X.sort()
  dist = []
  
  for i in range(M-1):
    dist.append(X[i+1] - X[i])
    
  dist.sort()
  ans = 0
  
  for i in range(M-N):
    ans += dist[i]
    
  print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
S=list(map(int,input().split()))
S.sort()
L=[0]*(M-1)
for i in range(M-1):
    L[i]=abs(S[i]-S[i+1])

L.sort()
goukei=0
if M-N>=1:
    for i in range(M-N):
        goukei+=L[i]
else:
    print(0)
    exit()
print(goukei)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
li = list(map(int,input().split()))
ans = []

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

li.sort()

for i in range(m-1):
    ans.append(li[i+1]-li[i])

ans.sort(reverse=True)
print(sum(ans[n-1:]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
if n>=m:
    print(0)
    exit()
x = sorted(map(int, input().split()))
l = sorted(j-i for i, j in zip(x, x[1:]))[::-1]
print(x[-1]-x[0]-sum(l[:n-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    if N >= M:
        print(0)
        return
    X.sort()
    distance = []
    for i in range(M-1):
        distance.append(X[i+1] - X[i])
    distance.sort()
    for _ in range(N-1):
        distance.pop()
    ans = sum(distance)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = sorted([int(i) for i in input().split()])
dx = []
for i in range(1, M):
    dx.append(abs(X[i] - X[i-1]))
dx = sorted(dx)
print(sum(dx[:max(M-N, 0)]))

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
pp = tuple(sorted(map(int, input().split())))

if n >= k:
    print(0)
    exit(0)

intv = []
for i in range(1, len(pp)):
    intv.append(pp[i] - pp[i - 1])
intv = sorted(intv)

ans = pp[-1] - pp[0]
for i in range(n - 1):
    ans -= intv[-i - 1]
print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))

    X.sort()
    Y = [0] * (M - 1)
    for i in range(M - 1):
        Y[i] = X[i + 1] - X[i]
    Y.sort(reverse=True)

    ans = sum(Y[N - 1:])
    print(ans)


if __name__ == "__main__":
    main()