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:
N, M = map(int, input().split())
X = list(map(int, input().split()))
X = sorted(X)


def main():
    if N > M:
        print(0)
        return

    #print(X)
    diff = [X[i+1] - X[i] for i in range(M-1)]
    #print(diff)
    diff = sorted(diff, reverse=True)
    #print(diff)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
import heapq

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

if n >= m:
    print(0)
else:
    npx = np.array(x)
    li = list(np.diff(npx, n = 1))

    print(sum(heapq.nsmallest(len(li)-n+1, li)))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
numlist = list(map(int,input().split()))
numlist.sort()
diflist = []

for i in range(M-1):
    diflist.append(numlist[i + 1] - numlist[i])
diflist.sort()
diflist.reverse()

delnum = N - 1
del diflist[:delnum]
sumnum = sum(diflist)

if M <= N:
    print("0")
else:
    print(sumnum)

Submission status: Accepted

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

X_difference.sort(reverse = True)
del X_difference[0:N-1:]
print(sum(X_difference))

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()
    y = []
    for i in range(len(x)-1):
        y.append(x[i+1]-x[i])
    y.sort()
    number = 0
    for i in range(len(y)-n+1):
        number = number + y[i]
    print(number)

Submission status: Accepted

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

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

X.sort()

sa = []
for i in range(0, M-1):
    ima_sa = X[i+1] - X[i]
    sa.append(ima_sa)

sa.sort()

for i in range(0, N-1):
    sa.pop()

kotae = sum(sa)
print(kotae)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
# ----------------------------------------------------------------
# Use Solve Function

def solve(lines):
    N,M = map(int, lines.pop(0).split(' '))
    X = list(map(int, lines.pop(0).split(' ')))
    if N >= M:
        print(0)
        sys.exit(0)
    X.sort()
    span = []
    for i in range(M-1):
        span.append( X[i+1] - X[i] )
    span.sort()
    for i in range(N-1):
        span.pop(-1)
    print(sum(span))

#
# main
#

lines = [x.strip() for x in sys.stdin.readlines()]

#
# solve !!
#
solve(lines)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
n, m = map(int, input().split())
l = sorted(list(map(int, input().split())))
divcount = n - 1
 
l1 = l[1:]
l2 = l[:m - 1]
divl = []
 
for i in range(m - 1):
    divl.append(l1[i] - l2[i])
 
divl.sort(reverse = True)
 
if n == 1:
    print(max(l) - min(l))
else:
    if m > n:
        for i in range(divcount):
            del divl[0]
    
        print (sum(divl))
    
    else:
        print(0)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
X=sorted(list(map(int,input().split())))
init=[]
tmp=0
i=1

if m<n:
  n=m

while i<len(X):
  init.append([X[i]-X[i-1],i])
  i+=1
init.sort(reverse=True,key=lambda x:x[0])
init=list(map(lambda x:x[1],init))
ans=0
init=sorted(init[:n-1])
if len(init)==0:
  print(X[-1]-X[0])
  exit()
tmp=0
for i in init:
  ans+=(X[i-1]-X[tmp])
  tmp=i
try:
  if i!=len(X)-1:
    ans+=X[-1]-X[i]
except IndexError:
  print(0)
  exit()
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
 
N,M=[int(i) for i in input().split()]
x=input().split()
y=[int(i) for i in x]
y.sort()
if(N==1):
    print(max(y)-min(y))
#    print(y[M-1]-y[0])
    exit()
if(M==1):
    print("0")
    exit()
if(N>=M):
    print("0")
    exit()
diff=[]
for i in range(M-1):
    diff.append(y[i+1]-y[i])
sub=[]
array=np.array(diff)
index=np.argsort(array)
c=index[-1::-1]
for i in range(N-1):
    sub.append(c[i])
ans=0
for i in range(N):
    if(i==0):
        ans+=y[sub[i]]-y[0]
    elif(i==N-1):
        ans+=y[M-1]-y[sub[i-1]+1]
    else:
        ans+=y[sub[i]]-y[sub[i-1]+1]
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
X = [int(v) for v in input().split()]
lx = len(X)

# N=10^5, M=10^5ならO(NM)は間に合わない

if N >= M:
    print(0)
else:
    # 動的計画法M個の地点を1~N個のコマで回ることを考える。

    X.sort()    # 昇順にソート
    coma = [0] * N
    # n=1
    diff = [x2-x1 for x2, x1 in zip(X[1:], X[:-1])]
    diff.sort() # 昇順にソート
    coma[0] = sum(diff)

    # n >= 2
    for i in range(1, N):
        coma[i] = coma[i-1] - diff[-1]
        del diff[-1]

    print(coma[-1])

Submission status: Accepted

Solution code:
import numpy as np

N, M = input().split()
N = int(N)
M = int(M)

if N >= M:
    print(0)
else:
    X_m = np.array(sorted(list(map(lambda x: int(x), input().split()))))
    X_m_sub = np.array(X_m[1:]-X_m[:-1])
    
    pos_option = X_m_sub.argsort()
    
    for n in range(N-1):
        X_m_sub[pos_option[-(n+1)]] = 0
    
    print(X_m_sub.sum())

Submission status: Accepted

Solution code:
import math

def solve(N,M,Xs):
    if N >= M:
        return 0

    Ds = [abs(Xs[i]-Xs[i+1]) for i in range(len(Xs)-1)] # Ds[j] := distance between j and j+1

    Ds.sort()
    #print(Ds)
    #print(math.ceil(N/2))

    #ntake = math.ceil(N/2)
    ntake = N-1

    return sum(Ds[0:len(Ds)-ntake])

def main():
    N, M = map(int, input().split())
    Xs = list(map(int, input().split()))
    Xs.sort()
    print(solve(N,M,Xs))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
num_lis = sorted(list(map(int, input().split())))
num_dif = []
ans = 0

if N > M:
  print(0)
elif M == 1:
  print(0)
else:
  for n in range(M):
    if n == M-1:
      break
    n_dif = num_lis[n+1] - num_lis[n]
    n_dif = abs(n_dif)
    num_dif.append(n_dif)
  sorted_num_dif = sorted(num_dif)
  if N == 1:
    ans = sum(sorted_num_dif)
  else:
    for i in sorted_num_dif[:-(N-1)]:
      ans += i

  print(ans)

Submission status: Accepted

Solution code:
a=input()
b=input()
c=a.split()
n=int(c[0])
d=b.split()
d=[int(i) for i in d]
d.sort(reverse=True)
count=0
ll=list()
for i in d:
    if count!=0:
        ll.append(c-i)
    c=i
    count+=1
ll.sort()
for i in range(n-1):
    ccc=len(ll)
    if ccc>=1:
        del ll[-1]
print(sum(ll))

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
X = np.array([int(x) for x in input().split()])

X.sort()

dif_X = X[1:] - X[:-1]
dif_X.sort()

if M - N <= 0:
  print(0)
else:
  print(sum(dif_X[:M-N]))

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
X = [x for x in map(int, input().split())]
sorted_x = sorted(X)
# print(sorted_x)
index = range(len(X)-1)
# print(index)
diff = [sorted_x[n+1] - sorted_x[n] for n in index]
sorted_diff = sorted(diff,reverse=True)
# print(sorted_diff)
sub_diff = sorted_diff[N-1:]
# print(sub_diff)
print(sum(sub_diff))

Submission status: Accepted

Solution code:
num, points_num = list(map(int, input().split(' ')))
points = list(map(int, input().split(' ')))

if num >= points_num:
    print("0")
else:
    points.sort()
    points = list(map(lambda x: [x], points))
    index = 0
    step = 1
    while num < len(points):
        # print(points, index, step)
        if index + 1 >= len(points):
            step = step + 1
            index = 0

        if points[index + 1][0] - points[index][-1] <= step:
            concat_arr = points.pop(index + 1)
            points[index].extend(concat_arr)
        else:
            index = index + 1
    # print(points)
    move_num = sum(list(map(lambda x: x[-1] - x[0], points)))
    print(move_num)

Submission status: Accepted

Solution code:
# encoding:utf-8

import copy
import numpy as np
import random
# import headpq

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

x = [int(i) for i in input().split()]

x_sorted = sorted(x)
dif_list = []
for i in range(m-1):
    dif_list.append(x_sorted[i+1]-x_sorted[i])

dif_list = sorted(dif_list)
answer = 0
for i in range((m-1)-(n-1)):
    answer += dif_list[i]

print(answer)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect

setrecursionlimit(10**7)

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, M = reads()
X = reads()
X.sort()
diff = [X[i] - X[i-1] for i in range(1, M)]
diff.sort()
i = max(M-N, 0)
print(sum(diff[:i]))

Submission status: Accepted

Solution code:
import numpy as np

N, M = map(int, input().split())
X_list = list(map(int, input().split()))
X_list.sort()

if M <= N:
    print(0)
elif N == 1:
    print(X_list[-1] - X_list[0])
else:
    diff = np.diff(X_list)
    ans = max(X_list) - min(X_list) - np.sum((-np.sort(-diff))[:N-1])
    print(ans)

Submission status: Accepted

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

if n>=m:
    print(0)
elif n==1:
    ans=max(x)-min(x)
    print(ans)
else:
    delta=[0]*(m-1)
    for i in range(m-1):
        delta[i]=x[i+1]-x[i]
    delta_s=sorted(delta)
    ans=sum(delta_s[:-n+1])
    print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
X_list = sorted(list(map(int, input().split())))
offset_list =[]
for x in range(len(X_list)):
    if x==0:
        continue
    offset = abs(X_list[x] - X_list[x-1])
    offset_list.append(offset)
offset_list.sort(reverse=True)
del offset_list[:N-1]
move_count = 0
for o in offset_list:
    move_count += o
print(move_count)

Submission status: Accepted

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


if N >= M or M == 1:
	ans = 0
elif N == 1:
	X.sort()
	ans = X[-1] -X[0]
else:
	X.sort()
	D = []
	for i in range(M-1):
		d = X[i+1] - X[i]
		D.append([i,d])
	#print(X)

	D.sort(key = lambda x:(x[1]),reverse =True)
	#print(D)
	sikiri = []
	for i in range(N-1):
		sikiri.append(D[i][0])
	sikiri.sort()
	ans = X[sikiri[0]] - X[0]
	for i in range(N-1):
		l = sikiri[i]+1
		if i == N-2:
			r = M-1
		else:
			r = sikiri[i+1]
		ans+= X[r]-X[l]
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()
    x1 = x[1:]
    x2 = x[:-1]
    xs = [_x1 - _x2 for _x1, _x2 in zip(x1, x2)]


    argxs = sorted(enumerate(xs), key=lambda y: y[1])

    a = []
    for i in range(1, n):
        a.append(argxs[-i][0])
    
    tmp = 0
    ans = 0

    for _a in a:
        ans += x[_a] - x[tmp]
        tmp = _a + 1
    ans += x[-1] - x[tmp]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

n,m=input().split()
N = int(n)
M = int(m)
X = input().split()
#MはXの要素の数
X = [int(x) for x in X]

X.sort()
if M == 1:
    print(0)
    sys.exit()
elif M < 1:
    sys.exit()

minus = [X[i]-X[i-1] for i in range(1,M)]
#print(minus)

minus.sort()
#print(minus)
sum_num = 0
if N < M:
    for i in range(M-N):
        sum_num += minus[i]
    print(sum_num)
elif N >= M:
    print(0)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
num = list(map(int, input().split()))
num_new = sorted(num)
gap = []

for i in range(m-1):
	gap.append(num_new[i+1] - num_new[i])

gap_new = sorted(gap, reverse=True)
del gap_new[0:n-1]
count = 0

for i in gap_new:
	count += i

print(count)

Submission status: Accepted

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

X_diff = []
for i in range(m - 1):
    X_diff.append(X[i + 1] - X[i]) 

X_diff = sorted(X_diff)

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

print(ans)

Submission status: Accepted

Solution code:
#ABC117C-Streamline.py

import numpy as np

INPUT = [int(n) for n in input().split()]
N, M = INPUT[0], INPUT[1]
X = [int(x) for x in input().split()]
X.sort()
Diff = []

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

Diff.sort()

for i in range(N-1):
    if Diff == []:
        break
    Diff.pop(-1)

print(int(np.sum(Diff)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
line1 = list(map(lambda x: int(x), input().split()))
N = line1[0]
M = line1[1]
X = list(map(lambda x: int(x), input().split()))

if N >= M or M == 1:
  print(0)
else:
  X.sort(key=lambda x:x, reverse=False)

  diff = list(map(lambda x: x[0]-x[1], zip(X[1:],X[:-1])))
  diff.sort(key=lambda s:s, reverse=False)

  if N == 1:
    print(sum(diff))
  else:
    print(sum(diff[:-(N-1)]))

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
X = [int(i) for i in input().split()]

X.sort()
if N == 1:
    print(X[-1]-X[0])

X.append(0)
A = []
for x, y in zip(X[:-1], X[1:]):
    A.append(y-x)
B = A[:-1]
C = sorted(B)

if N == 2:
    print(sum(C[:-1]))
elif N > 2:
    print(sum(C[:-N+1]))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, m = map(int, input().split())
    xs = sorted(int(s) for s in input().split())
    ds = [y - x for x, y in zip(xs[:-1], xs[1:])]
    ds.sort(reverse=True)
    print(sum(ds[n - 1:]))

Submission status: Accepted

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

X.sort()

result = 0
temp = []
if M <= N:
    print(0)
else:
    for i in range(M-1):
        temp.append(-(X[i] - X[i+1]))
    temp.sort()
    for i in range(M-N):
        result += temp[i]
    print(result)

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().split())
q = map(int,raw_input().split())

q.sort()

data = []

for a in range(1,len(q)):
  data.append( q[a] - q[a-1] )

data.sort()

for a in range( n-1 ):
 try:
  data.pop()
 except:
  pass

ans = 0

for a in range( len(data) ):
  ans += data[a]

print ans

Submission status: Accepted

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

Submission status: Accepted

Solution code:
Ns,Ms = input().split()
N=int(Ns)
M=int(Ms)
Ls = input().split()
ans=0
L=[]
Lx=[]
for i in range(M):
    L.append(int(Ls[i]))
L.sort()
for i in range(M-1):
    Lx.append(L[i+1]-L[i])
Lx.sort()
if N>=M:
    print(ans)
else:
    for i in range(M-N):
        ans=ans+Lx[i]
    print(ans)
# print(L)
# print(Lx)

Submission status: Accepted

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

x_list.sort()
ans = 0

margin = [0] * (M - 1)
f = x_list[0]
for i in range(1, M):
    margin[i - 1] = x_list[i] - f
    f = x_list[i]
margin = sorted(enumerate(margin), key=lambda x: (-x[1], x[0]))
cnt = [0]
for i, v in margin:
    if len(cnt) == N:
        break
    cnt.append(i + 1)

if len(cnt) == 1:
    p = -1
    for i, x in enumerate(x_list):
        if i == 0:
            p = x_list[0]
        else:
            ans += x_list[i] - p
            p = x_list[i]
    print(ans)
    exit()
start = 0
prev = x_list[0]
cnt.append(M)
cnt.sort()
for i, c in enumerate(cnt[1:]):
    for j in range(start, c):
        ans += x_list[j] - prev
        prev = x_list[j]
    if c != M:
        start = c
        prev = x_list[c]
print(ans)

Submission status: Accepted

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

if N == 1:
    ans = max(X) - min(X)
    print(ans)
    exit()

if ((M == 1) or (N >= M)):
    ans = 0
    print(ans)
    exit()

Xs = sorted(X)

diff = []
for i in range(M - 1):
    tmp = Xs[i + 1] - Xs[i]
    diff.append(tmp)

diffs = sorted(diff)
print(sum(diffs[:(M - 1) - (N - 1)]))

Submission status: Accepted

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

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):
    delta = X[i+1]-X[i]
    A.append(delta)

A.sort()
if len(A) > N-1:
    for i in range(N-1): 
        A.pop()
    print(sum(A))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys

lines = sys.stdin.readlines()
N, M = map(int, lines[0].split())
X = [int(x) for x in lines[1].split()]

X.sort()

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

diff.sort()
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()))
X.sort()

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

if M > N:

    difX = difX[N-1:]

    total = 0
    for x in difX:
        total+= x

    print(total)
else:
    print(0)

Submission status: Accepted

Solution code:
import numpy as np

N,M = map(int,input().split())
Xs = sorted([int(i) for i in input().split()])

if N >= M:
    print(0)
elif N == 1:
    print(Xs[-1]-Xs[0])
else:
    margin = [Xs[i+1]-Xs[i] for i in range(len(Xs)-1)]
    margin = [(i,x) for i,x in enumerate(margin)]
    point = [x[0] for x in sorted(margin,key=lambda x:x[1],reverse=True)[:N-1]]
    move = 0
    move += Xs[point[0]] - Xs[0]
    for i in range(1,len(point)):
        move += Xs[point[i]] - Xs[point[i-1]+1]
    move += Xs[-1] - Xs[point[-1]+1]
    print(move)

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()

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


#print(x)
y=np.array(x)
dy = y[1:]-y[:-1]
#print(dy)
dy.sort()
dy=dy[::-1]
#print(dy)
print(sum(dy[n-1:]))

"""
mi = min(dy)
ma = max(dy)
dy = np.append(dy,[ma+1])
print(dy)
for dif in range(mi,ma+1):
	if(len(dy[dy>dif]) <= n):
		lis = np.where(dy>dif)[0]
		print(dif)
		print(lis)
		s=sum(dy[0:lis[0]])
		print(s)
		for i in range(len(lis)-1):
			idx = lis[i]+1
			idx2 = lis[i+1]
			s += (sum(dy[idx:idx2]))
		break
print(s)




"""



"""
dp[i][j]	jまでの部分配列をi回分割した時の和の最小値

dp[0][j] = sum(dy[:j])
dp[i][j](i>=j) = NAN
dp[i][j](i=j-1) = 0
dp[i][j](i<j) = 
"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n_dices, n_points = map(int, input().split())
points = sorted(list(map(int, input().split())))
if n_dices >= n_points:
    print(0)
    sys.exit()
interval_list = [points[i + 1] - points[i] for i in range(n_points - 1)]
interval_list.sort(reverse = True)
print(sum(interval_list[n_dices - 1:]))

Submission status: Accepted

Solution code:
### C

N , M = list(map(int , input().split()))

X = list(map(int , sorted(list(map(int , input().split())))))

#print("X = " + str(X))

D = []

R = 0

if M-1 > 0 :
	for i in range(M-1):
		D.append(int(X[i+1]) - int(X[i]))


#print("D = " + str(D))

if D !=[]:
	D = sorted(D)
	D = D[::-1]
	D = D[N-1:]
#print("D = " + str(D))

if D != []:
	for d in D:
		R += d


print(R)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
list_x = list(map(int,input().split()))
list_sort = sorted(list_x)
if n >= m:
  print(0)
else:
  a = m - n
  list_A = []
  for i in range(m - 1):
    t = list_sort[i+1] - list_sort[i]
    list_A.append(t)
  list_B = sorted(list_A)
  s = 0
  for j in range(a):
    s += list_B[j]
  print(s)

Submission status: Accepted

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

if n >= m:
    print(0)
else:
    x.sort()
    y = [x[i+1]-x[i] for i in range(m-1)]
    z = sorted(y, reverse=True)
    a = []
    cnt = 0
    for i in range(n-1):
        dif = z.pop(0)
        idx = y.index(dif)
        a.append(idx)
    a.sort()
    x0 = x[0]
    for ai in a:
        cnt += x[ai] - x0
        x0 = x[ai+1]
    cnt += x[-1] - x0
    print(cnt)

Submission status: Accepted

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

lx.sort()
dx = []
s = 0

for i in range(len(lx)-1):
  dx.append(lx[i+1]-lx[i])

if n == 1:
  print(lx[m-1]-lx[0])
elif m <= n:
  print(0)
else:
  dx.sort()
  for i in range(len(dx)-n+1):
    s = s + dx[i]
  print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Feb  3 20:43:36 2019

@author: Owner
"""

# -*- coding: utf-8 -*-
"""
Created on Sun Jan 27 20:47:58 2019

@author: Owner
"""


import collections
import scipy.misc
import sys
import numpy as np
import math
from operator import itemgetter
import itertools
import copy

#素因数を並べる
def prime_decomposition(n):
  i = 2
  table = []
  while i * i <= n:
    while n % i == 0:
      n /= i
      table.append(int(i))
    i += 1
  if n > 1:
    table.append(int(n))
  return table   
# 桁数を吐く
def digit(i):
    if i > 0:
        return digit(i//10) + [i%10]
    else:
        return []
    
def getNearestValueIndex(list, num):
    """
    概要: リストからある値に最も近い値のインデックスを取得する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """

    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    return idx

"""
N, X = map(int, input().split())

x = [0]*N
x[:] = map(int, input().split())

P = [0]*N
Y = [0]*N
for n in range(N):
    P[n], Y[n] = map(int, input().split())
    
all(nstr.count(c) for c in '753')

ABT = zip(A, B, totAB)
result = 0
# itemgetterには何番目の配列をキーにしたいか渡します
sorted(ABT,key=itemgetter(2))
#A, B, totAB = zip(*ABT)

"""

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

X = [0]*M
X[:] = map(int, input().split())

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

X.sort()

if N == 1:
    print(X[M-1]-X[0])
    sys.exit()
else:
    pass

dX = [0]*(M-1)
for m in range(M-1):
    dX[m] = X[m+1] - X[m]
dX = np.array(dX)
dX_rank = dX.argsort()[::-1]

X_div = dX_rank[0:N-1]
X_div.sort()
result =0
cnt = 0
last_idx = 0

#print(X_div)
for nx in X_div:
    if cnt == 0:
        result = result + X[nx]-X[0]
        last_idx = nx
        cnt =+ 1         
    else:
        result = result + X[nx] - X[last_idx+1]
        last_idx = nx
    #print(result)
#print(X[-1], X[last_idx+1])
result = result + X[-1] - X[last_idx+1]

print(result)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

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

x2 = sorted(x)
y = []
for i in range(1, m):
    heapq.heappush(y, (-(abs(x2[i] - x2[i - 1]))))
for i in range(n - 1):
    heapq.heappop(y)
print(-(sum(y)))

Submission status: Accepted

Solution code:
import numpy as np

in_num = list(map(int, input().split()))
in_num2 = list(map(int, input().split()))
n = in_num[0]
m = in_num[1]
x = np.asarray(in_num2)

x = np.sort(x)
xsub = x[1:] - x[:-1] - 1

xsub = np.sort(xsub)[::-1]
xsum = np.max(x) - np.min(x)
xsub = np.sum(xsub[:n-1])
result = xsum + 1 - xsub - n
if result < 0:
    result = 0
print(result)

Submission status: Accepted

Solution code:
n, m = map(int,input().split())
a = [int(i) for i in input().split()]
a.sort()
sa  = []
for i in range(len(a)):
    if i == 0:
        continue
    tmp = max(a[i],a[i-1]) - min(a[i],a[i-1])
    sa.append(tmp)
sa.sort()
sa.reverse()
tmp = 0
for i, num in enumerate(sa):
    if i < n - 1:
        continue
    tmp += num
print(tmp)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, X):
    X.sort()
    diff = []
    for i in range(len(X)-1):
        diff.append(X[i+1] - X[i])
    diff.sort(reverse=True)
    diff = diff[N-1:]
    return sum(diff)


def main():
    # N = read_int()
    N, M = read_int_n()
    # A = [read_int_n() for _ in range(N)]
    X = read_int_n()
    print(slv(N, M, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if m <= n:
    print(0)
else:
    lis2 = [0]
    for i in range(m-1):
        lis2.append(int(abs(lis[i+1] - lis[i])))
    lis2.sort()
    lis2.reverse()
    del lis2[0:(n-1)]
    print(sum(lis2))

Submission status: Accepted

Solution code:
N_M = list(map(int ,input().split( )))
Xs = list(map(int ,input().split( )))
Xs.sort()

difference = []
for i in range(len(Xs)-1):
    difference.append(Xs[i+1] - Xs[i])
    
difference.sort()
sum_d = 0
for i in range(N_M[1] - N_M[0]):
    sum_d += difference[i]

print(sum_d)

Submission status: Accepted

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

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

D.sort(reverse=True)

sum = sum(D[N-1:])
print(sum)

Submission status: Accepted

Solution code:
def func():
    pass


def main():
    n, m = map(int, input().split())
    x = [int(i) for i in input().split()]

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

    x.sort()
    d = []
    for i in range(m - 1):
        d.append(x[i + 1] - x[i])

    top_n_d = sorted(d, reverse=True)[:n - 1]

    # print(x)
    # print(d)
    # print(top_n_d)

    print(max(x) - min(x) + 1 - sum(top_n_d) - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

if N > M:
    print(0)
    quit()

x_points.sort()

diffs = []
for x1, x2 in zip(x_points, x_points[1:]):
    diffs.append(x2-x1)

diffs.sort()
if  N == 1:
    print(sum(diffs))
    quit()

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter


def r(n, m, xl):
    if len(xl) == 1:
        return 0
    if n >= m:
        return 0
    xl.sort()
    min_x = abs(min(xl))
    xl = [x + min_x for x in xl]
    xm = [xl[i+1] - xl[i] for i in range(len(xl)-1)]
    xm.sort()
    xxb = xm[:m-n]
    return sum(xxb)


def main():
    input = sys.stdin.readline
    n, m = list(map(int, input().split()))
    xl = list(map(int, input().split()))

    print(r(n, m, xl))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m =list(map(int, input().split()))
xs = list(map(int, input().split()))
if n >= m:
    print(0)
    exit()
xs.sort()
if n == 1:
    print(abs(xs[0]-xs[-1]))
    exit()
a = [abs(xs[i] - xs[i+1]) for i in range(m-1)]
a.sort()
print(sum(a[:-n+1]))

Submission status: Accepted

Solution code:
def sol(n, S):
    if S is None or len(S) == 0: return 0
    S.sort() # sort in place
    #print(S)
    diffs = []
    pre = S[0]
    for i in range(1, len(S)):
        diffs.append(S[i] - pre)
        pre = S[i]
    diffs.sort(reverse=True)
    #print(diffs)
    for x in range(n-1):
        if len(diffs) > 0:
            del diffs[0]
    return sum(diffs)



test = False
if test:
    n, m = 2, 5
    S =list( map(int, "10 12 1 2 14".split()))
    print(sol(n, S))

    n, m = 3, 7
    S =list( map(int, "-10 -3 0 9 -100 2 17".split()))
    print(sol(n, S))

    n, m = 100, 1
    S =list( map(int, "-100000".split()))
    print(sol(n, S))


else:
    n, m = map(int, input().split())
    S =list( map(int, input().split()))
    #print(n, S)
    print(sol(n, S))

Submission status: Accepted

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


Xs.sort()
costs=[abs(Xs[i]-Xs[i+1]) for i in range(M-1)]
costs.sort(reverse=True)

for i in range(N-1):
    if not costs:
        print(0)
        exit(0)
    costs.pop(0)




print(sum(costs))

Submission status: Accepted

Solution code:
def main():
    n, m = [int(x) for x in input().split()]
    x = [int(x) for x in input().split()]
    if n >= m:
        return 0
    x.sort()
    dxs = [x2 - x1 for x1, x2 in zip(x, x[1:])]
    dxs.sort()
    return sum(dxs[:m - n])

print(main())