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())
L=list(map(int,input().split()))
L=sorted(L)
S=[]
if N>=M:
	print(0)
	exit()
for i in range(M-1):
	S.append(abs(L[i+1]-L[i]))
S=sorted(S)
#print(S)
print(sum(S[0:M-N]))

Submission status: Accepted

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

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

X.sort(reverse=True)

d = [0]

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

d.sort(reverse=True)
if N >= M:
    print(0)
else:
    print(sum(d)-sum(d[0:N-1]))

Submission status: Accepted

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

Submission status: Accepted

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

x.sort()
sub = [0] * (m - 1)
tmp = x[0]
for i in range(1,m):
    sub[i-1] = x[i] - tmp
    tmp = x[i]
sub.sort(reverse=True)

ans = sum(sub[:n-1])
print(x[-1]-x[0]-ans)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
x=sorted(list(map(int,input().split())))
y=[0]*(m-1)
for i in range(m-1):
  y[i]=x[i+1]-x[i]
y=sorted(y)
if n==1:
  print(sum(y))
else:
  print(sum(y[:-(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()
d=[]
for i in range(1,m):
  d.append(abs(x[i]-x[i-1]))
d.sort()
print(sum(d[:m-n]))

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

Submission status: Accepted

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

if n >= m:
    print(0)
else:
    d = []
    x.sort()
    for i in range(m-1):
        d.append(x[i+1]-x[i])
    d.sort()
    ans = 0
    for i in range(m-n):
        ans += d[i]
        #print(d[i])
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np 

n, m = map(int, sys.stdin.readline().split())
x = np.array(sys.stdin.readline().split(), dtype=np.int64)
x.sort()

def main():
    d = np.sort(x[1:] - x[:-1])[::-1]
    d = np.concatenate((np.array([0]), np.cumsum(d)))
    res = d[m-1] - d[min(n, m) - 1]
    print(res)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np 

n, m = map(int, sys.stdin.readline().split())
x = np.array(sys.stdin.readline().split(), dtype=np.int64)
x.sort()

def main():
    if n >= m:
        print(0)
        return
    d = x[1:] - x[:-1]
    d = np.sort(d)[::-1]
    np.cumsum(d, out=d)
    res = d[-1]
    res -= 0 if n == 1 else d[n-2]
    print(res)

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    #各コマについて「行って引き返して」とやることは完全に無駄であることから、
    #各コマは一度動いたらその方向にしか動かないものと思うことが出来る
    #さらに進む方向はX軸方向の正の向きとしていい
    #そう考えると各こまは
    #・数直線上の区間(長さが0であってもよい)
    #と同一視してよいことが分かる。
    #つまり、N個の区間によって、M個の座標を完全に被覆する問題
    #ここで、これらの区間の両端点は、M個の座標として指定されているチェックポイント部分
    #のみに限定してよいことが分かる
    #https://drken1215.hatenablog.com/entry/2019/02/03/224100
    #さらに、これは補集合をとると、
    #・N-1箇所の覆われていない「隣り合う2点」
    #に対応していることが分かる。
    #これを最大にすればいいことが分かる
    #よって問題は、「隣り合う2点」の距離を表すM-1個の数値を大きい順にソートして
    #大きい順にN-1個を足す(M-1個に達したら終了)
    n,m = readInts()
    X = readInts()
    #昇順に
    X = sorted(X)
    d = [0] * (m-1)
    for i in range(len(X)-1):
        d[i] = X[i+1] - X[i]
    d = sorted(d,reverse=True)
    #print(d)
    print(sum(d[n-1:]))
if __name__ == '__main__':
  main()

Submission status: Accepted

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

d_ls = [0] * m
for i in range(1,m):
    d_ls[i] = x_ls[i] - x_ls[i-1]
d_ls.sort(reverse = True)
print(x_ls[-1] - x_ls[0] - sum(d_ls[:n-1]))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,m=map(int,input().split())
    X=[int(_) for _ in input().split()]
    if m<=n:
        print(0)
    else:
        X.sort()
        XX=[0]*(m-1)
        for i in range(m-1):
            XX[i]=X[i+1]-X[i]
        XX.sort(reverse=True)
        print(X[-1]-X[0]-sum(XX[:n-1]))

if __name__=='__main__':
    main()

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

L = [abs(X[i] - X[i + 1]) for i in range(0, M - 1)]
L.sort(reverse=True)

ans = (X[-1] - X[0]) - sum(L[:N - 1])
print(ans)

Submission status: Accepted

Solution code:
import itertools
N,M = map(int,input().split())
ary1 = map(int,input().split())
if N>=M:
  print(0)
else:
  ary2 = sorted(list(ary1))
  ary3 = ary2[1:]
  ary4 = ary2[:-1]
  d1  = ary2[M-1]-ary2[0]
  dist1 = sorted([i-j for i,j in zip(ary3,ary4)])[M-N:M]
  d2 =  sum(dist1)
  print(d1-d2)

Submission status: Accepted

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

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

if N >= M:
  print(0)

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

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

Submission status: Accepted

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

if n >= m:
    print(0)
else:
    x = list(sorted(x))
    ku = []
    for i in range(len(x)-1):
        ku.append(abs(x[i]-x[i+1]))
    #print(ku)
    ku = list(sorted(ku))
    
    print(sum(ku[:m-n]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
if m <= n:
    print(0)
    exit()

x.sort()

dif = [0] * (m-1)
for i in range(m-1):
    dif[i] = x[i+1] - x[i]

dif.sort()
print(sum(dif[:m-n]))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
henka=[]
ans=[10**5+1]*3
ans=0
if m<=n:
    print(ans)
else:
    for i in range(m-1):
        sa=x[i+1]-x[i]
        henka.append(sa)
            
    henka.sort()
    for i in range(m-n):
        ans+=henka[i]
    print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
x = list(map(int, input().split()))
x.sort()
dist = [j - i for i, j in zip(x, x[1:])]
dist.sort(reverse=1)
print(sum(dist[n-1:]))

Submission status: Accepted

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


def kansu(N,M,X):

    x_abs = [X[m+1] -X[m] for m in range(M-1)]    
#    print(x_abs)

    
    x_abs.sort()

    koma_max = 0
    for m in range(M-N):
        koma_max += x_abs[m]

    print(koma_max)


N,M,X = nyu()
#print(X)

if M == 1:
    print(0)
else:
    kansu(N,M,X)

#print(S)

Submission status: Accepted

Solution code:
# from math import factorial,sqrt,ceil
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

import numpy as np
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix

# strlist = "abcdefghijklmnopqrstuvwxyz"
n,m = map(int,input().split())
# arrX = list(map(int,input().split()))
X = np.array(input().split(),dtype=np.int64)

X.sort()
X = np.diff(X)
X.sort()

if n>=m:
    ans = 0
elif n == 1:
    ans = X.sum()
else:
    ans = X[:-(n-1)].sum()

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))

Submission status: Accepted

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

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

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

if m <= n:
    print(0)
else:
    x.sort()
    diff = []#i番目とi+1番目の距離
    for i in range(m-1):
        diff.append(x[i+1] - x[i])
    diff.sort(reverse=True)
    # print(diff)
    if n > 1:
        for i in range(n-1):
            diff.pop(0)
    # print(diff)
    print(sum(diff))

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

X.sort()

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

dist = []

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

dist.sort(reverse=True)

ans = X[-1] - X[0]
for i in range(N-1):
    ans -= dist[i]
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x=list(map(int,input().split()))
"""
2 5
10 12 1 2 14
1 2 10 12 14
->5
3 7
-10 -3 0 9 -100 2 17
-100 -10 -3 0 2 9 17
->19
100 1
-100000
->0
"""
if n >= m:
  print(0)
else:
  x.sort()
  xd=[]
  xp=x[0]
  for xi in x[1:]:
    xd.append(xi-xp)
    xp=xi
  xd.sort(reverse=True)
  print(sum(xd[n-1:]))

Submission status: Accepted

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

dlist = [0]*(m-1)
for i in range(m-1):
  dlist[i] = xlist[i+1]-xlist[i]
dlist.sort()
ans = 0

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

print(ans)

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(m-1):
        D.append(X[i+1]-X[i])
    D.sort()
    print(sum(D[:m-n]))

Submission status: Accepted

Solution code:
# abc133_b.py
N, M = map(int,input().split())
X = list(map(int,input().split()))
X.sort()
Xsub = [X[i+1]-X[i] for i in range(M-1)]
Xsub.sort(reverse=True)
print(sum(Xsub[N-1:]))

Submission status: Accepted

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

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

x.sort()

dis = [0] * (m - 1)

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

dis.sort()

cnt = 0
for i in range(m - n):
    cnt += dis[i]
    
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

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

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

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

Submission status: Accepted

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

if N >= M:
    print(0)
else:
    Dist = [0]*(M-1)
    for i in range(M-1):
        Dist[i] = X[i+1] - X[i]
        Sum += Dist[i]

    Dist.sort(reverse=True)
    for j in range(N-1):
        Sum -= Dist[j]

    print(Sum)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
X = sorted(map(int, input().split()))
d = [0] * (m-1)
for i in range(m-1):
    d[i] = abs(X[i] - X[i+1])
d.sort(reverse=True)
print(sum(d[n-1:]))

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(M - 1):
        Y.append(X[i + 1] - X[i])
    Y.sort()
    print(sum(Y[:M - N]))

Submission status: Accepted

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

X = sorted(X)
list = [10000]*(M-1)

if N >= M:
	print(0)
else:
	for i in range (0, M-1):
		list[i]=X[i+1]-X[i]		
	K = sorted(list)
	print(sum(K[0:M-N]))

Submission status: Accepted

Solution code:
import collections

n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
l = []
for i in range(m-1):
    l.append(abs(x[i]-x[i+1]))
dec = collections.deque(sorted(l))
if n > 1:
    for _ in range(n-1):
        if len(dec) == 0:
            break
        dec.pop()

print(sum(dec))

Submission status: Accepted

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

x.sort()

for i in range(m-1):
  base[i] = x[i+1] - x[i]
  
base.sort()
ans = 0

for i in range(m-n):
  ans = ans + base[i]
  
print(ans)

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 += [X[i + 1] - X[i]]
Y.sort()
# 担当する区間の個数の和
print(sum(Y[:max(0, M - N)]))

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()
    if ans is not None:
        print(ans)


def solve():
    N, M = iip(False)
    X = iip()
    X.sort()

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

    return sum(A[0:max(0, M-N)])


#####################################################ライブラリ集ここから

def iip(listed=True, num_only=True):  # 数字のinputをlistで受け取る
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

if n >= m:
  print(0)
  
else:
  List.sort()
  dis = []
  for i in range(1, len(List)):
    dis.append(List[i] - List[i-1])
  dis.sort()
  res = 0
  for i in range(len(dis)-(n-1)):
    res += dis[i]
  print(res)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = list(map(int, input().split()))
d = [0]*(m-1)
k.sort()
for i in range(m-1):
    d[i] = abs(k[i]-k[i+1])
d = sorted(d, reverse=True)
print(sum(d)-sum(d[:n-1]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
k = list(map(int, input().split()))
d = [0]*(m-1)
k.sort()
for i in range(m-1):
    d[i] = abs(k[i]-k[i+1])
d = sorted(d, reverse=True)
res = 0
for i in range(n-1):
    if i==m-1:
        break
    res += d[i]
print(sum(d)-res)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    b = []
    for i in range(m-1):
        b.append(a[i+1] - a[i])
    b.sort()
    if n < m:
        print(sum(b[:m-n]))
    else:
        print(0)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

X =sorted(X)

dis = [X[i+1]-X[i] for i in range(len(X)-1)]
dis = sorted(dis)

ans = 0
for i in range(len(dis)-n+1):
    ans = ans + dis[i]
    
print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from fractions import gcd
import numpy as np
readline = sys.stdin.readline
INF = 10**9


def main():
  N, M = map(int, readline().split())
  X = np.array(readline().split(), dtype=np.int64)
  X.sort()
  X = np.diff(X)
  X.sort()
  if M-N>=0:
    answer = X[:M-N].sum()
  else:
    answer = 0
  print(answer)
  
  
  
  
  
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: # コマのほうが多い場合
    print(ans)
    exit()
 
X.sort() # ソートする
x_diff = [0]*M 
for i in range(1, M):
    x_diff[i-1] = X[i] - X[i-1]
x_diff.sort(reverse=True)
ans = sum(x_diff[N-1:]) # 切れ目のN-1こめまでは、Nこのコマが担当するので移動しなくて良い
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n, m = map(int, input().split())
x = deque(sorted(list(map(int, input().split()))))
popleft = x.popleft
work = [0 for i in range(m-1)]
for i in range(m-1):
    temp = popleft()
    work[i] = x[0] - temp
work.sort(reverse=True)
print(sum(work[n-1:]))

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,m = LI()
x = LI()
x.sort()
lst = []
for i in range(m-1):
    lst.append(x[i+1]-x[i])
lst.sort(reverse=1)
if n >= m:
    print(0)
    quit()
print(sum(lst[n-1:]))

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=[0]*(m-1)
  for i in range(m-1):
    d[i]=x[i+1]-x[i]
  d.sort(reverse=True)
  print(sum(d[(n-1):]))

Submission status: Accepted

Solution code:
def main():
    n, m, *x = map(int, open(0).read().split())
    if n >= m:
        print(0)
        return
    x.sort()
    a = [x[i + 1] - x[i] for i in range(m - 1)]
    a.sort()
    if n == 1:
        print(sum(a))
        return
    ans = sum(a) - sum(a[-n+1:])
    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: # コマのほうが多い場合
    print(ans)
    exit()

X.sort()
x_diff = [0]*M
for i in range(1, M):
    x_diff[i-1] = X[i] - X[i-1]
x_diff.sort(reverse=True)
ans = sum(x_diff[N-1:])
print(ans)

Submission status: Accepted

Solution code:
def solve():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    X.sort()
    diff = []
    for i in range(M-1):
        diff.append(X[i+1] - X[i])
    
    diff.sort(reverse=True)
    print(X[-1] - X[0] - sum(diff[:min(N,M)-1]))

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

x.sort(reverse=True)
print(sum(x[N-1:]))

Submission status: Accepted

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

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

x=sorted(x)[::-1]
print(sum(x[N-1:]))

Submission status: Accepted

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

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

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

x.sort()
interval = [0] * (M - 1)
for i in range(M - 1):
    interval[i] = x[i + 1] - x[i]

interval.sort(reverse=True)
ans = 0
if N != 1:
    for i in range(N - 1):
        ans += interval[i]
    print(sum(interval) - ans)
else:
    print(sum(interval))

Submission status: Accepted

Solution code:
import sys

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

if N >= M:
    print(0)
    sys.exit()
    
s= [0]*(M-1)
for i in range(M-1):
    s[i] = X[i+1] - X[i]
s.sort(reverse=True)
res = sum(s)
if M == 1:
    res = 0
else:
    for i in range(N-1):
        res -= s[i]
print(res)

Submission status: Accepted

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

    lst = list(map(int, input().split()))
    lst.sort()
    if N>=M:
        print(0)
        return

    diff = []
    for i in range(M-1):
        diff.append(lst[i+1] - lst[i])
    diff.sort()
    
    if N==1:
        print(sum(diff))
    else:
        rmdiff = diff[:-(N-1)]
        print(sum(rmdiff))
main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
x = list(map(int, input().split()))
if N >= M:
    print(0)
    quit()


x.sort()
s = [0] * (M - 1)
for i in range(M - 1):
    s[i] = x[i + 1] - x[i]

s.sort(reverse=True)

res = sum(s)
if M == 1:
    print(0)
    quit()
else:
    for i in range(N - 1):
        res -= s[i]

print(res)

Submission status: Accepted

Solution code:
import heapq
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
x_diff = [b-a for b, a in zip(x[1:], x[:-1])]
x_diff.sort()
if n >= m:
    print(0)
else:
    # dp[n] n個の駒で取りうる最小の手数
    # dp[n] = dp[n-1] - {n-1駒の守備範囲で最も大きい空白の長さ}
    dp = [0] * (n+1)
    dp[1] = x[-1] - x[0]
    for i in range(2, n+1):
        dp[i] = dp[i-1] - x_diff.pop(-1)
    print(dp[n])

Submission status: Accepted

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

Submission status: Accepted

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

X.sort()

x = X[:]
p = x.pop(0)
a = []
for b in x:
    a.append(b - p)
    p = b

if a:
    a.sort(reverse=True)
    print(sum(a[N-1:]))
else:
    print(0)

Submission status: Accepted

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

if M <= N:
    print(0)
else:
    dists = sorted(X[i] - X[i - 1] for i in range(1, M))
    print(sum(dists[:M - N]))

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
l = [0]*(M)
for i in range(1,M):
    l[i] = x[i]-x[i-1]
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()))
if n >= m:
    print(0)
    exit()
x.sort()
y = [x[i+1]-x[i] for i in range(m-1)]
y.sort(reverse = True)
count = x[m-1]-x[0]
count -= sum(y[:n-1])
print(count)

Submission status: Accepted

Solution code:
from sys import stdin

N, M = map(int, stdin.readline().split())
X = list(map(int, stdin.readline().split()))

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

X.sort()
dists = []

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

# print(dists)

dists.sort(reverse=True)

ans = 0

for i in range(N - 1, M - 1):
    ans += dists[i]

print(ans)

Submission status: Accepted

Solution code:
def solution():
    n, m = map(int, input().split())
    x = list(map(int, input().split()))
    x.sort()
    diff = [j - i for i, j in zip(x, x[1:])]
    diff.sort()
    ans = sum(diff[:m-n]) if m-n > 0 else 0
    print(ans)

solution()

Submission status: Accepted

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

Submission status: Accepted

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


distance=sorted(distance, reverse=True)
#print(distance)
answer=sum(distance[(N-1):])
print(answer)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = sorted(list(map(int,input().split())))
cnt = []
for i in range(m-1):
  cnt.append(x[i+1] - x[i])
cnt = sorted(cnt)
if n == 1:
  print(x[-1] - x[0])
else:
  print(sum(cnt[:-(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:
  Y = []
  for i in range(M-1):
    Y.append(X[i+1] - X[i])

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

Submission status: Accepted

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

Submission status: Accepted

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