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:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

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

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

n,m = MI()
x = RI()

x.sort()
ls = []
for i in range(m-1):
    d = abs( x[i+1] - x[i] )
    ls.append(d)
ls.sort(reverse=True)
print(sum(ls[n-1:]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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



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

Submission status: Accepted

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

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

    B = sorted(B,reverse = True)
    print(sum(B[N-1:]))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]

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

x.sort()

sa=[]

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

sa.sort()

ans=0

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

Submission status: Accepted

Solution code:
def INT():
    return int(input())

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

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

N, M = MI()
X = LI()
X.sort()

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

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

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

Submission status: Accepted

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

import sys
# sys.setrecursionlimit(100000)


def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, m = input_int_list()
    X = sorted(input_int_list())
    diffs = []
    for i in range(1, m):
        diffs.append(abs(X[i - 1] - X[i]))
    diffs = sorted(diffs)
    ans = sum(diffs[:m - n])
    if n >= m:
        print(0)
        return
    else:
        print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

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

x = sorted(x)

#print("x",x)

y = []

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

y = sorted(y, reverse=True)

#print("y",y)

skip = 0
for i in range(n-1):
    skip += y[i]

print(max(x)-min(x)-skip)

Submission status: Accepted

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

total = max(x) - min(x)
if n >= m:
    print(0)
elif n == 1:
    print(total)
else:
    gap = []
    for i,j in zip(x, x[1:]):
        gap.append(j-i)
    gap.sort(reverse=True)
    print(total - sum(gap[: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)
else:
  Y = []
  for i in range(M-1):
    Y.append(X[i+1] - X[i])
  Y.sort(reverse=True)
  print(X[-1] - X[0] - sum(Y[: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:
  nums = [0]*(m-1)
  for i in range(m-1): nums[i] = x[i+1] - x[i]
  nums.sort()
  print(sum(nums[:m-n]))

Submission status: Accepted

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

h = []
ans = 0

if N < M:
    for i in range(M-1):
        h.append(X[i+1] - X[i])
    h = sorted(h)
    ans = max(ans, sum(h[:M - N]))

print(ans)

Submission status: Accepted

Solution code:
'''
Created on 2020/08/28

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,M=map(int,pin().split())
  X=list(map(int,pin().split()))
  if N>=M:
    print(0)
    return
  X.sort()
  d=[]
  for i in range(M-1):
    d.append(abs(X[i]-X[i+1]))
  d.sort()
  print(sum(d[:M-N]))
  return 
main()
#解説AC

Submission status: Accepted

Solution code:
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def main():
    n, m = LI()
    x = sorted(list(LI()))
    diff = []
    if m == 1:
        print(0)
    else:
        for i in range(1, m):
            diff.append(x[i] - x[i - 1])
        print(sum(diff) - sum(sorted(diff, reverse=True)[:n-1]))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

d = []
for i in range(1, m):
    d.append(x[i]-x[i-1])
d.sort()
d.reverse()
print(sum(d)-sum(d[:n-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n,m = LI()
    x = LI()
    x.sort()
    lst = []

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

Solution code:


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

X.sort()
cnt = 0
arr = [0]*(M-1)
if N >= M:
    ans = 0
else:
    for i in range(1,M):
        arr[i-1] = (abs(X[i-1]-X[i]))
    #print(arr)
    arr.sort()
    ans = sum(arr[0:M-N])
print(ans)

Submission status: Accepted

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

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

x.sort()

dists = []
point = x.pop(0)
for xs in x:
    dists.append(xs-point)
    point = xs
dists.sort(reverse=True)

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#n = int(input())
n, m = map(int, input().split())
xl = list(map(int, input().split()))
#al=[list(input()) for i in range(n)]
xl.sort()
difl = []

for i in range(1, m):
    difl.append(xl[i]-xl[i-1])

difl.sort(reverse=True)

if n >= m:
    ans = 0
else:
    ans = xl[-1]-xl[0]-sum(difl[:n-1])
print(ans)

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
sys.setrecursionlimit(500*500)
import itertools
from collections import Counter,deque

def main():
    n,m = map(int, input().split())
    l = list(map(int, input().split()))
    l.sort()

    ans = 0
    if n<m:
        L = []
        for i in range(m-1):
            L.append(l[i+1] - l[i])
        L.sort()
        for i in range(m-n):
            ans += L[i]
    print(ans)

if __name__=="__main__":
    main(
    )

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
if N >= M:
    print(0)
    exit()
X = list(map(int, input().split()))
X.sort(reverse=True)
dist = []
for i in range(1, M):
    dist.append(X[i] - X[i - 1])
dist = list(map(lambda x: (-1) * abs(x), dist))
heapq.heapify(dist)
#print(dist)
for _ in range(N - 1):
    heapq.heappop(dist)
ans = -1 * sum(dist)
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)

elif N == 1:
    print(abs(max(X) - min(X)))

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

Submission status: Accepted

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

def main(n,m,x):
    if m<=n:
        return 0
    xs=sorted(x)
    #print(xs)
    d=[]
    for i in range(m-1):
        d.append((xs[i+1]-xs[i],i+1))
    ds=sorted(d,reverse=True,key=lambda x:x[0])
    c=[0]*m
    for i in range(n-1):
        c[ds[i][1]]+=1
    #print(c)
    ans=0
    for i in range(1,m):
        if c[i]==0:
            ans+=xs[i]-xs[i-1]
    return ans

if __name__=='__main__':
    n,m,x=readinput()
    ans=main(n,m,x)
    print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = [int(i) for i in input().split()]
x.sort()
if n >= m:
    ans = 0
else:
    x_sa = [x[i+1]-x[i] for i in range(m-1)]
    x_sa.sort(reverse = True)
    if n >1:
        del x_sa[:(n-1)]
    ans = sum(x_sa)
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)
    exit()
dis = [x[i+1]-x[i] for i in range(m-1)]
dis.sort()
if n>1:
    del dis[-(n-1):]
print(sum(dis))

Submission status: Accepted

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

Submission status: Accepted

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

    if n >= m:
        return 0
    diff_list =[0]
    for i in range(m-1):
        diff_list.append(pos_list[i+1]-pos_list[i])
    diff_list.sort()
    #print(pos_list)
    #print(diff_list)
    if n==1:
        return sum(diff_list)
    return sum(diff_list[:-n+1])

print(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()
Y = [(X[i+1]-X[i]) for i in range(M-1)]
Y.sort()

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

Submission status: Accepted

Solution code:
import sys
n,m=map(int,input().split())
x=sorted(list(map(int,input().split())))
dp=[0]*(m-1)
ans=0

if n>=m:
  print(0)
  sys.exit()
for i in range(m-1):
  dp[i]=x[i+1]-x[i]
dp.sort()

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = list(map(int,input().split()))
t_3 = max(x) - min(x)
t = []
t_2 = 0
x.sort()
if m == 1:
    print(0)
    exit()

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

t.sort(reverse=True)
pp = min(n-1,m-1)
for i in range(pp):
    t_2 += t[i]

print(t_3-t_2)

Submission status: Accepted

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

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

X.sort()
D=[]
for i in range(1,m):
    D.append(X[i]-X[i-1])

D.sort(reverse=True)
d=0
if i>1:
    for i in range(min(n-1,m-1)):
        d += D[i]    

ans = sum(D)-d
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
if N>M:
    print(0)
    exit()
lst=list(map(int,input().split()))
lst.sort()
sum_1=max(lst)-min(lst)
D=[]
for i in range(1,M):
    D.append(lst[i]-lst[i-1])
D.sort(reverse=True)
sum_2=0
for i in range(N-1):
    sum_2+=D[i]
ans=0
ans=sum_1-sum_2
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *X = map(int, read().split())

    if N >= M:
        print(0)
        return

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

    dist.sort()
    ans = sum(dist[: M - N])

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import heapq

N, M = map(int, input().split()) # N個の駒、M個の地点
X = list( map(int, input().split())) #駒の座標


if N >= M:
    ans = 0
else:
    X.sort()
    distance = [0] * (M-1)
    for i in range(M-1):
        distance[i] = -abs(X[i+1] - X[i])

    sum_distance = sum(distance)
    heapq.heapify(distance)

    count = 0 
    for _ in range(N-1):
        max_num = heapq.heappop(distance)
        count += max_num

    ans = abs(sum_distance - count)

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import math

n, m = map(int, input().split(" "))
xL = sorted(list(map(int, input().split(" "))))

diff = [0 for _ in range(m - 1)]

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

diff = sorted(diff, reverse=True)

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

s = 0

if n >= m:
    s = 0
else:
    x.sort()
    d = []
    for j in range(m-1):
        d.append(x[j+1]-x[j])
    d.sort()
    s = sum(d[:m-n])

print(s)

Submission status: Accepted

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

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

X.sort()

memo = []

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

memo.sort()
#print(memo)
ans = 0
for i in range(M-N):
    ans += memo[i]
print(ans)

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    x = sorted(list(map(int, input().split())))
    diff = list()

    for i, j in zip(x, x[1:]):
        diff.append(abs(i - j))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int, input().split())
X = sorted(np.array(input().split(), dtype = np.int64))
X = sorted(np.diff(X))
if m-n >= 0:
    ans = sum(X[:m-n])
else:
    ans = 0
print(ans)

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

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

Submission status: Accepted

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

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

diffs.sort()
ans = sum(diffs[:selected])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def get_section_arr(X):
    return [(X[i+1]-X[i]) for i in range(len(X)-1) ]
if __name__ == "__main__":
    N,M = map(int,input().split())
    X = list(map(int,input().split()))
    X.sort()
    section_arr = get_section_arr(X)
    section_arr.sort(reverse=True)
    print((X[-1]-X[0]) - (sum(section_arr[:N-1])))

Submission status: Accepted

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

if n >= m:
    ans = 0
else:
    x.sort()
    kyori = [x[i]-x[i-1] for i in range(1,m)]
    kyori.sort()
    ans = sum(kyori[0:m-n])
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
X = list(map(int, input().split()))
 
if N>=M: print(0)
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:
def main():
  N, M = list(map(lambda a: int(a), input().split(" ")))

  if N >= M:
    print(0)
    return 0
  
  X = list(map(lambda x: int(x), input().split(" ")))
  X.sort()
  D = [X[i+1] - X[i] for i in range(len(X) - 1)]
  D.sort()
  print(sum(D[:M-N]))

main()

Submission status: Accepted

Solution code:
import sys
import math


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, M = map(int, input().split())
    X = list(map(int, input().split()))
    X.sort()
    if M <= N:
        print(0)
        exit()

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x = sorted(list(map(int,input().split())))
if n>=m:
  print(0)
else: 
  step = []
  div = []
  num = []
  for i in range(m-1):
    step.append([x[i+1]-x[i],i+1])
  step.sort(reverse=True)
  for i in range(n-1):
    num.append(step[i][1])
  num.sort()
  temp = []
  for i in range(m):
    if len(num)!=0:
      if i==num[0]:
        div.append(temp)
        del num[0]
        temp = []
    temp.append(x[i])
  div.append(temp)
  ans = 0
  for l in div:
    ans += l[-1]-l[0]
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

dis = [0]*(M-1)

for i in range(M-1):
  dis[i] = X[i+1] - X[i]

dis.sort()

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
	n,m = map(int,input().split())
	A = list(map(int,input().split()))
	A.sort()

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

	B = []
	for i in range(m-1):
		#差分を求める
		B.append(A[i+1] - A[i])
	B.sort()
	
	print(sum(B[:m-n]))

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

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

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input()) for _ in range(n) ]

# ddict = defaultdict(lambda: 0)
# ddict = defaultdict(lambda: 1)
# ddict = defaultdict(lambda: int())
# ddict = defaultdict(lambda: list())
# ddict = defaultdict(lambda: float())

n,m = MI()
x = RI()

x.sort()
# print(x)

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

sa.sort(reverse=True)
# print(sa)

ans = sum(sa[n-1:])
print(ans)

Submission status: Accepted

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

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

x=sorted(x)

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

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

Submission status: Accepted

Solution code:
#1 コマは片方の方向に動かした方が効果的
#2 コマをはじめにおく位置は訪れるべき整数の方がよい
#3 M個の区間で覆うその長さの総和がコマの総移動距離になる
#4 M個の区間の最小値=M個の区間で覆われてない区間の最大値を最大にすればいい
#5 M個の区間で覆うということは覆われてない区間はmー１個ある
#6 よって区間の最大値を求めて上からm-1個選べばいい

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

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

Submission status: Accepted

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

new_X=sorted(X)


if M<=N:
    print(0)

elif N==1:
    print(new_X[-1]-new_X[0])

else:
    numbers=[]
    for m in range(M-1):
        number=new_X[m+1]-new_X[m]
        numbers.append(number)
    new_numbers=sorted(numbers)
    for _ in range(N-1):
        del new_numbers[-1]
    print(sum(new_numbers))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

x = sorted(x)
dist = [x[i+1] - x[i] for i in range(len(x) - 1)]

dist = sorted(dist)

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

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()
diff=[x[i+1]-x[i] for i in range(m-1)]
#print(diff)
print(sum(sorted(diff)[:m-n]))

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    Xs = sorted(list(map(int, input().split())))
    Xs_diff = []
    if n >= m:
        print(0)
        exit()

    for i in range(1, m):
        Xs_diff.append(Xs[i]-Xs[i-1])

    Xs_diff.sort()
    ans = sum(Xs_diff[:(m-n)])
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, m = nm()
    X = nl()
    X = sorted(X)
    D = [X[i + 1] - X[i] for i in range(m - 1)]
    D = sorted(D, reverse=True)
    print(sum(D[n - 1:]))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


stdin = sys.stdin
def ns(): return stdin.readline().rstrip()
def ni(): return int(stdin.readline().rstrip())
def nm(): return map(int, stdin.readline().split())
def nl(): return list(map(int, stdin.readline().split()))


def main():
    n, m = nm()
    X = nl()
    if n >= m:
        print(0)
    else:
        X = sorted(X)
        D = [X[i + 1] - X[i] for i in range(m - 1)]
        D = sorted(D, reverse=True)
        print(sum(D[n - 1:]))


if __name__ == '__main__':
    main()