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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

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

X.sort()

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

Y=sorted(Y)[:-(N-M)]
print(sum(Y))

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()
y = []
for i in range(1,m):
    y.append(x[i] - x[i-1])
y.sort(reverse = True)
ans = sum(y)
ans2 = sum(y[:n-1])
print(ans - ans2)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
koma_pos = [0]

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

distance.sort(reverse=True)

res = 0
for i in range(min(n - 1, len(distance))):
    tmp, index = distance[i]
    koma_pos.append(index)

koma_pos.sort()
koma_pos.append(m)
for i in range(min(n, len(koma_pos) - 1)):
    l = koma_pos[i]
    r = koma_pos[i + 1]
    res += x[r - 1] - x[l]

print(res)
# print(koma_pos)
# print(distance)
# print(x)

Submission status: Accepted

Solution code:
k, n = list(map(int, input().split()))
x = list(map(int, input().split()))
x.sort()
df = [0] * (n - 1)
for i in range(n - 1):
    df[i] = abs(x[i + 1] - x[i])

df = sorted(df, reverse=True)
print(sum(df[k - 1 :]))

Submission status: Accepted

Solution code:
import math
import sys
import collections
import bisect


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys
import collections
import bisect


def main():
    n, m = map(int, input().split())
    x = sorted(list(map(int, input().split())))
    if m <= n:
        print(0)
        return
    y = sorted([x[i + 1] - x[i] for i in range(m - 1)])
    print(sum(y[0:(m-n)]))


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)
else:
  X = sorted(X)
  list = [X[i]-X[i-1] for i in range(1,M)]
  list = sorted(list)
  list1 = list[:M-N]
  print(sum(list1))

Submission status: Accepted

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

Submission status: Accepted

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

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    x = sorted(list(map(int, input().split())))
    if n >= m:
        print(0)
    else:
        dis = []
        for i in range(m - 1):
            dis.append(x[i + 1] - x[i])
        dis.sort(reverse=True)
        print(max(x) - min(x) - sum(dis[:n - 1]))



if __name__ == '__main__':
    main()

Submission status: Accepted

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

p=[]
for x in range(m-1):
    p.append(a[x+1]-a[x])

if n==1:print(sum(p));exit()
print(sum(sorted(p)[:1-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()
diff = []
sum_dist = X[-1] - X[0]

for i, x in enumerate(X):
    diff.append(x - X[i - 1])


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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instr = lambda: sys.stdin.readline()
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()
X = inintl()

X.sort()
diff = []

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

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:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

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

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

Submission status: 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_sort=sorted(b,reverse=1)
print(sum(b_sort[n-1:]))

Submission status: Accepted

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

x.sort()
ans_list=[]
for i in range(1,m):
  ans_list.append(x[i]-x[i-1])
ans_list.sort(reverse=True)

print(max(x)-min(x)-sum(ans_list[:n-1]))

Submission status: Accepted

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

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

x_diff.sort()

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

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split()))
X = list(map(int,input().split()))
sortedX = sorted(X)
deltaList = []
for i in range(len(sortedX) - 1):
    delta = sortedX[i + 1] - sortedX[i]
    deltaList.append(delta)
sortedDeltaList = sorted(deltaList)
answer = 0
count = M - 1 - N + 1
if count <= 0:
    answer = 0
else:
    for i in range(count):
        answer += sortedDeltaList[i]
print(answer)

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()
print(sum(Y[:max(0,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.sort()
  delta_X = [X[i]-X[i-1] for i in range(1,M)]
  delta_X.sort()
  print(sum(delta_X[0:M-N]))

Submission status: Accepted

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

# from numba import njit

import itertools
from bisect import bisect_right,bisect_left

INF = 10**10

# @njit
def solve(n,m,x):
  if n >= m:
    return 0
  else:
    d = list(sorted(x[i+1] - x[i] for i in range(m-1)))[::-1]
    res = x[-1] - x[0]
    for i in range(min(m-1,n-1)):
        res -= d[i]
    return res

def main():
  N,M = map(int,input().split())
  x = sorted(list(map(int,input().split())))
  print(solve(N,M,x))
  return

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

X = sorted(X)

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

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

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

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

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

Submission status: Accepted

Solution code:
import sys

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

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

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

X.sort()

D = sorted(abs(X[i+1] - X[i]) for i in range(M-1))

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

Submission status: Accepted

Solution code:
import sys

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys

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

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

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

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

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

Submission status: Accepted

Solution code:
import math
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
ans = 0
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[:n-1]))

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
y=[]
for i in range(len(x)-1):
  y+=[x[i+1]-x[i]]
y.sort()
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()

if N>=M:
    print(0)
else:
    d=[]
    for i in range(1,M):
        d.append(X[i]-X[i-1])
    d.sort()
    print(sum(d[:M-N]))

Submission status: Accepted

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

import numpy as np

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

x = np.array(sorted(Xs))
if N == 1:
    print(np.sum(np.sort(np.diff(x))))
else:
    print(np.sum(np.sort(np.diff(x))[:-N+1]))

Submission status: Accepted

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

dis = []
if m <= n:
    print(0)
else:
    x.sort()
    for i in range(m - 1):
        dis.append(abs(x[i] - x[i + 1]))
    dis.sort()
    print(sum(dis[:m - n]))

Submission status: Accepted

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

dis = []
if m <= n:
    print(0)
else:
    x.sort()
    for i in range(m - 1):
        dis.append(abs(x[i] - x[i + 1]))
    dis.sort()
    sum(dis[- n + 1:])
    print(sum(dis[:m - n]))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, m = map(int, input().split())
*x, = map(int, input().split())
x.sort()
d = sorted(x[i] - x[i - 1] for i in range(1, m))
print(sum(d[:m - n]) if m > n else 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()
  Y = []
  for i in range(len(X) - 1):
    Y.append(X[i + 1] - X[i])
  Y.sort()
  print(sum(Y[:M - N]))

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int, input().split())
x = np.array([int(i) for i in input().split()])
x = np.sort(x)
d = np.diff(x)
d = np.sort(d)[::-1]
if m < n:
    ans = 0
else:
    '''
    x ---+---+----------+-+----+-
    d    3   10         1 4    -
    このとき、d = 3,1の点を選んでいる
    なぜ？
        d = 10で分割している
    分割したあとは、左から距離を足せばおｋ
    分割の回数はn-1個 -> dの大きいものからn-1個除去し、残りのsumを取る
    '''
    ans = d[n-1:].sum()
print(ans)

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

Submission status: Accepted

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

if N >= M:
    print(0)

else:
    ls.sort()
    long1 = ls[-1]-ls[0]

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

    ls2.sort(reverse=True)
    des = 0
    for i in range(N-1):
        des += ls2.pop(0)

    print(long1-des)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, m, *x = map(int, read().split())
    if n >= m:
        print(0)
        sys.exit()
    x.sort()
    sa = []
    pre = x[-1]
    for xe in x:
        sa.append(abs(xe - pre))
        pre = xe
    sa.sort()
    num = m - n
    r = sum(sa[:num])
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

# list X をソート O(Mlog(M)) する
# 駒を置いて残る目的地 (X_i, ..., X_j) に対して、訪れない区間の長さ最大化する
# 駒２個目以降をおくたびに、訪れないで済む区間が一つ増える
N, M = map(int, readline().split())

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

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

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

L.sort(reverse=True)

res = X[M-1] - X[0] - sum(L[:N-1])

print(res)

Submission status: Accepted

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

cnt = sorted([x[i] - x[i - 1] for i in range(1, m)])
print(sum(cnt[:m-n]) if m > n else 0)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy
 
## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))
 
N,M = map(int, input().split())
X = list(map(int, input().split()))


X.sort()

ans = X[M-1] - X[0]
tmp = []

if N==1:
    print(ans)
    sys.exit()


for i in range(1,M):
    tmp2 = X[i] - X[i-1]
    if len(tmp) < N-1:
        tmp.append(tmp2)
    else:
        tmp3 = min(tmp)
        if tmp3 < tmp2:
            tmp.remove(tmp3)
            tmp.append(tmp2)

print(ans - sum(tmp))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
val = []
if n >= m:
    print(0)
    exit()

for i in range(m-1):
    p = x[i+1]-x[i]
    val.append(p)
val.sort()
print(sum(val[:m-n]))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
X = tuple(map(int, input().split()))
X = sorted(X)
dx = []
for px, bx in zip(X[:m], X[1:]):
    dx.append(bx-px)
if n >= m:
    print(0)
else:
    dx = sorted(dx, reverse=True)
    print(sum(dx[n-1:]))

Submission status: Accepted

Solution code:
import sys
N, M = list(map(int, input().split()))
X = list(map(int, input().split()))
if M == 1:
    print(0)
    sys.exit()
X.sort()
_X = [X[i + 1] - X[i] for i in range(M - 1)]
_X.sort()
res = sum(_X)
for i in range(min(N - 1, M - 1)):
    res -= _X[M - 2 - i]
print(res)

Submission status: Accepted

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

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

d = [0] * (m-1)
x.sort()

for i in range(m-1):
  d[i] = x[i+1] - x[i]
d.sort(reverse=True)
mx = x[-1] - x[0]
r = n - 1
dsum = sum(d[:r])
print(mx - dsum)

Submission status: Accepted

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

a=sorted(a)
b=[]

for x in range(m-1):
  c=a[x+1]-a[x]
  b.append(c)
  

b=sorted(b)
if n>=m:
  print(0)
  
else:
  nn=m-n
  ans=0
  for u in range(nn):
    ans+=b[u]
    
  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)])[::-1]
print(max(X)-min(X)-sum(Y[:N-1]))

Submission status: Accepted

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

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

L = sorted(L, reverse=True)

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

Submission status: Accepted

Solution code:
import sys

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

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

x.sort()
dis = [0] * (m)
for i in range(1, m):
    dis[i] = abs(x[i] - x[i - 1])
dis.sort()

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

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

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

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

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

    X = lmi()
    X.sort()

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

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

    return

main()

Submission status: Accepted

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


x.sort()
diff = []
f = x[0]
if m <= n:
    print(0)
else:

    for i in x[1:]:
        diff.append(i-f)
        f = i

    diff.sort()
    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()
xx=[]
for i in range(len(x)-1):
  if len(x)==1:
    xx.append(x[0])
    break
  s=x[i+1]-x[i]
  xx.append(s)
  
xx.sort(reverse=True)
ans=sum(xx[n-1:])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

X = sorted(X)

anslis = []


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


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

anslis = sorted(anslis)

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

Submission status: Accepted

Solution code:
import sys
N,M = [int(x) for x in input().split()]
X = [int(x) for x in input().split()]
if N >= M:
    print(0)
    sys.exit()
X = sorted(X)
dis = [0 for x in range(M-1)]
for i in range(M-1):
    dis[i] = X[i+1] - X[i]
dis.sort()
dis.reverse()
for i in range(N-1):
    dis[i] = 0
print(sum(dis))

Submission status: Accepted

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

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

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

kyori =sorted(org_kyori)

ans = sum(kyori)
for i in range(N-1):
    ans -= kyori[-1*(i+1)]

print(ans)

Submission status: Accepted

Solution code:
#C

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

x.sort()
length = []
if n >= m:
    print(0)
else:
    #長い道ををm-n個取っておく
    for i in range(m - 1):
        length.append(x[i + 1] - x[i])
    length.sort()
    tmp = sum(length[(m - n):])
    print(x[m-1]-x[0] - tmp)
    # print(x[m-1],length)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')


def solve():
    n, m = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    a.sort()
    ans = a[-1] - a[0]
    b = []
    for i in range(m-1):
        b.append(a[i+1] - a[i])
    b.sort(reverse=True)
    for i in range(min(len(b), n-1)):
        ans -= b[i]
    print(ans)
        

t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""


"""

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc117


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

    if N >= M:
        return 0

    if N == 1:
        return X[-1] - X[0]

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

    ds_sort = sorted(ds, key=lambda x: x[0], reverse=True)
    jump = ds_sort[:N-1]
    jump = sorted(jump, key=lambda x: x[1])

    ans = 0
    j = 0
    for i in range(M-1):
        if j < len(jump) and i == jump[j][1]:
            j += 1
            continue

        ans += ds[i][0]

    return ans


print(main())

Submission status: Accepted

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

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

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

Submission status: 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

sys.setrecursionlimit(10000000)

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

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

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

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


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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys

def main():
    input = sys.stdin.readline
    n,m = map(int, input().split())
    x_list = list(map(int, input().split()))
    if n >= m:
        print(0)
        exit(0)
    sabun_list = []
    x_list.sort()
    for i,x in  enumerate(x_list):
        if i == 0:
            continue
        sabun_list.append(x - x_list[i-1])
    result = 0
    sum_max_sabun = 0
    sabun_list.sort(reverse=True)
    sum_max_sabun = sum(sabun_list[:n-1])
    
    result = (x_list[-1] - x_list[0]) - sum_max_sabun

    print(result)

    return


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

Submission status: Accepted

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

    diffs = []
    for i in range(M-1):
        diffs.append(abs(X[i+1]-X[i]))
    diffs.sort(reverse=True)
    print(X[M-1]-X[0]-sum(diffs[:N-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:
  L = sorted([X[i + 1] - X[i] for i in range(M - 1)], reverse=True)
  print(X[-1] - X[0] - sum([L[i] for i in range(N - 1)]))

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import deque
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

n,m = readInts()
x = readInts()
x.sort()

if m==1:
  print(0)
  exit()

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

ans = x[-1]-x[0]
for i in range(min(n-1,len(intval))):
  ans-=intval[i]

print(ans)

Submission status: Accepted

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

    else:
        print(0)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
X = sorted(li())

sa = []

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

sa = sorted(sa)
#print(sa)
print(sum(sa[:max(M-N, 0)]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import sys
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect

sys.setrecursionlimit(10**6)
def zz():
    return list(map(int, sys.stdin.readline().split()))


def z():
    return int(sys.stdin.readline())


def S():
    return sys.stdin.readline()


def C(line):
    return [sys.stdin.readline() for _ in range(line)]


N, M = zz()
X = zz()
X = sorted(X)
if (M <= N):
    print(0)
    exit()
distance = [0]*(M-1)
for i in range(M-1):
    # print(X[i+1] - X[i])
    distance[i] = X[i+1] - X[i]
distance = sorted(distance, reverse=True)
distance = distance[N-1:]
print(sum(distance))

Submission status: Accepted

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

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

if N > 1:
    print(sum(Xsub[:-(N-1)] ))   
else:
    print(sum(Xsub))