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

Submission status: Accepted

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

xs = sorted(xn)
ln = []
for i in range(0, m-1):
    ln.append(xs[i+1] - xs[i])

ls = sorted(ln)
if n>=m:
    print(0)
else:
    print(sum(ls[:(m-n)]))

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
X = sorted(list(map(int, input().split())))
I = sorted([X[m+1]-X[m] for m in range(M-1)])
print(sum(I[:max(M-N,0)]))

Submission status: Accepted

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

x = sorted(x)
diff = [x[i+1]-x[i] for i in range(m-1)]
diff = sorted(diff)
print(sum(diff[:len(diff)-(min(n,m)-1)]))

Submission status: Accepted

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

# ソートして、差が大きい区間をサボるようにコマを配置すればよい
Y = sorted(X)
ans = sum(
    sorted(
        (
            a - b
            for a, b in zip(Y[1:], Y)
        ),
        reverse=True
    )[(N - 1):]
)

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = sorted([int(x) for x in input().split()])
if N >= M:
    print(0)
    exit()
diff = []
for i, x in enumerate(X):
    if i == 0:
        diff.append((0, 0))
        continue
    diff.append((i, X[i] - X[i - 1]))
diff.sort(key=lambda x: x[1], reverse=True)
indices = sorted([e[0] for e in diff[:N-1]])
start = 0
step = 0
for end in indices:
    step += X[end - 1] - X[start]
    start = end
step += X[-1] - X[start]
print(step)

Submission status: Accepted

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

#print(X)

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

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

#print(diff)

diff.sort(key=lambda x: x[1], reverse=True)

#print(diff)

indices = sorted([e[0] for e in diff[:N-1]])
start = 0
step = 0

#print(indices)

for end in indices:
    step += X[end - 1] - X[start]
    start = end
step += X[-1] - X[start]
print(step)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
lst = list(map(int,input().split()))
def wake(n,m,li):
    li2 = []
    li.sort()
    for i in range(m-1):
        cur = li[i+1]-li[i]
        li2.append([cur,i])
    li2.sort(key=lambda x: x[0],reverse = True)
    li3 = [x[0] for x in li2[n-1:]]
    return sum(li3)
if N >= M:
    ans = 0
else:
    ans = wake(N,M,lst)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

X = sorted(X)
diff_dict = {}
for i in range(M-1):
    diff = X[i+1] - X[i]
    diff_dict[i] = diff
sorted_diff = sorted(diff_dict.items(), key=lambda x: x[1])[::-1][:N-1]
keys = {x[0] for x in sorted_diff}
tmp = []
count = 0
for i, x in enumerate(X):
    tmp.append(x)
    if i in keys:
        if len(tmp) > 1:
            count += (max(tmp) - min(tmp))
        tmp.clear()
if len(tmp) > 1:
    count += (max(tmp) - min(tmp))
print(count)

Submission status: Accepted

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

X =  sorted(X)
d = []

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

    d = sorted(d)
    del d[len(d)-N+1:len(d)]
    S = sum(d)
    print(S)

Submission status: Accepted

Solution code:
# ABC117C - Streamline
def main():
    n, m = map(int, input().split())
    lst = sorted(set(map(int, input().split())))
    dis = []
    for i, j in zip(lst, lst[1:]):
        dis += [j - i]
    print(sum(sorted(dis, 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()))
if N >= M:
    print(0)
else:
    sortX = sorted(X)
    diffX = [sortX[i+1] - sortX[i] for i in range(M-1)]
    print(sortX[-1]-sortX[0]-sum(sorted(diffX, reverse=True)[:N-1]))

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def gcd(a, b):
    if a == 0:
        return b
    if b == 0:
        return a

    if a > b:
        return gcd(b, a % b)
    else:
        return gcd(a, b % a)


def gcd_multi(nums):
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return nums[0]

    ret = gcd(nums.pop(), nums.pop())
    while len(nums) > 0:
        ret = gcd(ret, nums.pop())
    return ret


def solve(inputs):
    [N, M] = string_to_int(inputs[0])
    targets = string_to_int(inputs[1])

    if N >= M:
        return 0

    targets.sort()
    diffs = []
    for i in range(0, len(targets)-1):
        diffs.append((i, targets[i+1] - targets[i]))
    diffs.sort(key=lambda x: x[1])

    # separate groups
    separaters = []
    for _ in range(0, N-1):
        separaters.append(diffs.pop()[0])
    separaters.sort()

    groups = []
    prev_sep = -1
    for i, s in enumerate(separaters):
        groups.append(targets[prev_sep+1:s+1])
        prev_sep = s
    groups.append(targets[prev_sep+1:])

    counts = 0
    for g in groups:
        counts += g[-1] - g[0]

    return counts


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(2))
    print(ret)

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

  diffs = [0]*(M-1)

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

  diffs.sort(key= lambda x: -x)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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


main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
A=list(map(int,input().split()))
A.sort()
B=[]
total=0
for i in range(1,M):
    B.append(A[i]-A[i-1])
B.sort()

for i in range(M-N):
    total +=B[i]
print(total)

Submission status: Accepted

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

Submission status: Accepted

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

d = tuple(sorted((xr - xl for xr, xl in zip(x[1:], x)), 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 = [x[i+1]-x[i] for i in range(m-1)]
    y.sort()
    sp = 0
    for i in range(n-1):
        sp += y[-i-1]
    print(x[m-1]-x[0]-sp)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()
to=M-N
if to<=0:
    ans=0
else:
    ans=sum(diff[:to])
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)
    exit()

diff = sorted([X[i] - X[i - 1] for i in range(1, M)])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split()) # 横に2個
X = list(map(int, input().split()))

if N >= M:
    ans = 0
else:
    X = sorted(X)
    dif = []
    for i in range(M-1):
        dif.append(X[i+1] - X[i])
    dif.sort(reverse=True)
    ans = X[M-1] - X[0] - sum(dif[:N-1])

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
a,b = map(int,input().split())
lis = list(map(int,input().split()))
lis.sort()
ls=[]
for i in range(b-1):
    ls.append(lis[i+1]-lis[i])
ls.sort(reverse=True)
print(sum(ls[a-1:]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

ans = 0
for i in range(M-N):
    ans += B[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

x = sorted(X)
diff = []
for n in range(1, M):
	diff.append(x[n] - x[n - 1])
diff.sort(reverse=True)

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

Submission status: Accepted

Solution code:
a, b = map(int, input().split())
if a >= b:
    print(0)
else:
    c = list(map(int, input().split()))
    c.sort()
    d = []
    for i in range(1, b):
        d.append([abs(c[i] - c[i-1]), i])
    d = sorted(d, key=lambda x: x[0], reverse=True)
    e = []
    for i in range(a-1):
        e.append(d[i])
    e.sort()
    f = []
    for i in range(len(e)):
        f.append(c[e[i][1]])
        f.append(c[e[i][1]-1])
    f.append(c[0])
    f.append(c[len(c)-1])
    f.sort()
    g = 0
    for i in range(1, len(f), 2):
        g += f[i] - f[i-1]
    print(g)

Submission status: Accepted

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

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

    diff = []

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

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

Submission status: Accepted

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

xl.sort()
xd = np.diff(xl)
sxd = sorted(xd)

if n > m :
    ans = 0
else :
    ans = sum(sxd[:m-n])

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

if N >= M:
  print(0)
else:
  X.sort()
  npX = np.array(X)
  D = npX[1:] - npX[:-1]
  D.sort()
  print(sum(D[0:M-N]))

Submission status: Accepted

Solution code:
from heapq import heapify, heappop, heappush, nsmallest
n, m = map(int, raw_input().split())
X = map(int, raw_input().split())
X.sort()
if m == 1:
    print 0
    exit()
elif n == 1:
    print X[-1] - X[0]
    exit()
heap = []
heapify(heap)
for i in range(1, m):
    diff = X[i] - X[i-1]
    if len(heap) >= n - 1 and heap[0][0] < diff:
        heappop(heap)
        heappush(heap, (diff, X[i-1], X[i]))
    elif len(heap) < n - 1:
        heappush(heap, (diff, X[i-1], X[i]))
    else:
        continue
heap.sort(key=lambda X : X[1])
cp = X[0]
move = 0
for j in range(len(heap)):
    diff, left, right = heap[j]
    move += left - cp
    cp = right
move += (X[-1] - cp)
print move

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

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

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

Submission status: Accepted

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

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

gap = []


if( n >= m):
    print(0)
    exit()
else:
    x = sorted(x)
    for i in range(m-1):
        gap.append(x[i+1] - x[i])
    gaps = sorted(gap)

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

Submission status: Accepted

Solution code:
import sys

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

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

gap = []


if( n >= m):
    print(0)
    sys.exit()
else:
    x = sorted(x)
    for i in range(m-1):
        gap.append(x[i+1] - x[i])
    gaps = sorted(gap)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = list(map(int, input().split()))
x_sub = [0] * (M -1)

X = sorted(X, key = lambda x: x)

for i in range(len(X) - 1):
    x_sub[i] = X[i+1] - X[i]

x_sub = sorted(x_sub, key = lambda x: -x)


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

Submission status: Accepted

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

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

dist.sort()
dist.reverse()

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

Submission status: Accepted

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

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

dist.sort()
dist.reverse()

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

Submission status: Accepted

Solution code:
# editorialを参考にした
# M個の目的地があると、そこには(M-1)個の区間がある。N個のコマを使うことで(N-1)個の区間を訪れなくてもよくなる。
# つまり、長い区間を(N-1)個除いて、それ以外の区間の和が移動回数の最小値
N, M = map(int, input().split())
X = [int(x) for x in input().split()]
X = sorted(X)
sa = [0] * (M - 1)
for i in range(M - 1):
    sa[i] = X[i + 1] - X[i]
sa = sorted(sa)
numofmove = 0
if N >= M:
    numofmove = 0
else:
    for j in range(M - N):
        numofmove += sa[j]

print(numofmove)

Submission status: Accepted

Solution code:
# ediitorialを参考にした
# M個の目的地があると、そこには(M-1)個の区間がある。N個のコマを使うことで(N-1)個の区間を訪れなくてもよくなる。
# つまり、長い区間を(N-1)個除いて、それ以外の区間の和が移動回数の最小値
N, M = map(int, input().split())
X = [int(x) for x in input().split()]
X = sorted(X)
sa = [0] * (M - 1)
for i in range(M - 1):
    sa[i] = X[i + 1] - X[i]
sa = sorted(sa)
numofmove = 0
if N >= M:
    numofmove = 0
else:
    for j in range(M - N):
        numofmove += sa[j]

print(numofmove)

Submission status: Accepted

Solution code:
# ediitorialを参考にした
N, M = map(int, input().split())
X = [int(x) for x in input().split()]
X = sorted(X)
sa = [0] * (M - 1)
for i in range(M - 1):
    sa[i] = X[i + 1] - X[i]
sa = sorted(sa)
numofmove = 0
if N >= M:
    numofmove = 0
else:
    for j in range(M - N):
        numofmove += sa[j]

print(numofmove)

Submission status: Accepted

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

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

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

dist_l.sort()
print(sum(dist_l[:-(n-1)]) if n !=1 else sum(dist_l))

Submission status: Accepted

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


if n>=m:
    print(0)
else:
    cnt =0
    for i in range(m-n):
        cnt +=ans[i]
    print(cnt)

Submission status: Accepted

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

if N >= M:
    print(0)
elif N == 1:
    print(sum(X_interval))
else:
    print(sum(X_interval[:-(N - 1)]))

Submission status: Accepted

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

d = []
for i in range(M-1):
    d.append(abs(l[i+1]-l[i]))
d = list(sorted(d))
while N != 1 and len(d) !=0:
    del d[len(d)-1]
    N -= 1
sum = 0
if len(d) >= 1:
    for i in range(len(d)):
        sum += d[i]
print(sum)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
x_dif=[b-a for a,b in zip(x[:-1],x[1:])]
x_dif.sort(reverse=True)
print(sum(x_dif[(n-1):]))

Submission status: Accepted

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

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

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(reverse=True)
if n>=m:
  print(0)
else:
  print(sum(b[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] - x[i - 1] for i in range(1, len(x))]
y_sort = sorted(y, reverse=True)
z = [y_sort[i] for i in range(N - 1)]
print(sum(y) - sum(z))

Submission status: Accepted

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

Submission status: Accepted

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

if n >= m:
  print(0)
else:
  li = sorted(li)
  diff = [0]*(m-1)
  for i in range(m-1):
    diff[i] = li[i+1] - li[i]
  diff = sorted(diff)
  if n == 1:
    print(sum(diff))
  else:
    print(sum(diff[:-n+1]))

Submission status: Accepted

Solution code:

import sys

n1, n2  = [int(i) for i in input().split()]

na3 = [int(j) for j in input().split()]

if n1 >= n2:
    print("0")
    sys.exit()

na3.sort()

na4 = []
for i5 in range(n2):
    if i5 != 0:
        na4.append(na3[i5] - na3[i5 -1])

na4.sort(reverse=True)
n6 = 0
for i7 in range(n1 -1):
    n6 += na4[i7]

r7 = sum(na4) - n6

print(r7)

Submission status: Accepted

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

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

Submission status: Accepted

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

dat_x.sort()
dat_x = list(map(lambda x: x + (1-dat_x[0]), dat_x))

if m == 1:
    print(0)
elif(n == m):
    print(0)
else:
    distance = [0] * (m)
    for i in range(m - 1):
        distance[i] = dat_x[i+1] - dat_x[i]
    distance.sort(reverse=True)
    distance = distance[n - 1:]
    print(sum(distance))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N, M = nl()
Xs = nl()
if N >= M:
    print(0)
    import sys
    sys.exit()

Xs = sorted(Xs)
Ls = []
for i in range(1, len(Xs)):
    Ls.append(Xs[i] - Xs[i-1])
Ls = sorted(Ls, reverse=True)
print(sum(Ls) - sum(Ls[:N-1]))

Submission status: Accepted

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

dis = []
for i, j in zip(lst, lst[1:]):
    dis += [j - i]
    
print(sum(sorted(dis, reverse=True)[n - 1:]))

Submission status: Accepted

Solution code:
# ABC117C - Streamline
def main():
    n, m = list(map(int, input().rstrip().split()))
    lst = sorted(set(map(int, input().rstrip().split())))
    dis = []
    for i, j in zip(lst, lst[1:]):
        dis += [j - i]
    print(sum(sorted(dis, reverse=True)[n - 1 :]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC117C - Streamline
def main():
    n, m = list(map(int, input().rstrip().split()))
    lst = sorted(list(map(int, input().rstrip().split())))
    dis = []
    for i, j in zip(lst, lst[1:]):
        dis += [j - i]
    print(sum(sorted(dis, reverse=True)[n - 1 :]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC117C - Streamline
def main():
    n, m = list(map(int, input().rstrip().split()))
    lst = sorted(list(map(int, input().rstrip().split())))
    dis = []
    cur = lst[0]
    for i in lst:
        dis += [i - cur]
        cur = i
    print(sum(sorted(dis, reverse=True)[n - 1 :]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
X = [int(i) for i in input().split()]
if N >= M:
  print(0)
  exit()

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

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

Submission status: Accepted

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

x.sort()
diffx = [x[i+1]-x[i] for i in range(M-1)]
diffx.sort(reverse = True)

if M == 1:
    print(0)
else:
    tmp = sum(diffx[:(N-1)])
    print(x[-1] - x[0] - tmp)

Submission status: Accepted

Solution code:
import heapq
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N, M = map(int, input().split())
X = list(map(int, input().split()))

X.sort()
dif_X = []
move = [[X[M - 1]] * 2 for _ in range(N)]

for i in range(M - 1):
	heapq.heappush(dif_X, (X[i] - X[i + 1], i))
	
move[0][0] = X[0]

for i in range(N - 1):
	if len(dif_X) > 0:
		tmp = heapq.heappop(dif_X)
		move[i][1] = X[tmp[1]]
		move[i + 1][0] = X[tmp[1] + 1]

move[N - 1][1] = X[M - 1]
ans = 0

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

xlist.sort()
#print(xlist)

xintv=[-1]*(M-1)
for i in range(M-1):
  xintv[i]=xlist[i+1]-xlist[i]
  
xintv.sort()
#print(xintv)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = sorted(list(map(int, input().split())))
dif = []
pos = []
ans = 0

if n >= m:
    print(0)
elif n == 1:
    print(x[-1] - x[0])
else:
    for i in range(m - 1):
        dif.append([x[i + 1] - x[i], i])

    dif.sort(reverse = True)

    for i in range(n - 1):
        pos.append(dif[i][1])

    pos.sort()

    ans += x[pos[0]] - x[0]
    for i in range(n - 2):
        ans += x[pos[i + 1]] - x[pos[i] + 1]
    ans += x[m - 1] - x[pos[-1] + 1]

    print(ans)

Submission status: Accepted

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

if M<=N:
    print(0)

else:
    diff = []
    List = sorted(List)
    for i in range(M-1):
        diff.append(List[i+1]-List[i])
    print(List[-1]-List[0]-sum(sorted(diff, reverse=True)[:N-1]))

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
    n, m = [int(e) for e in input().split()]
    xm = [int(e) for e in input().split()]
    xm.sort()
    dif = [xm[i + 1] - xm[i] for i in range(m - 1)]
    dif.sort()
    print(sum(dif[:max(0, m - n)]))


main()

Submission status: Accepted

Solution code:
# 左から歩いてN-1区間スキップ
import numpy as np
N,M = map(int,input().split())
X = np.array(input().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)

Submission status: Accepted

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

cost=[0 for _ in range(M-1)]

for i in range(1,M):
    cost[i-1]=X[i]-X[i-1]

cost.sort(reverse=True)

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
zahyou = list(map(int,input().split()))
zahyou.sort()
difference = []
ans = 0

if N >= M:
    ans = 0
else:
    for i in range (M-1):
        difference.append(zahyou[i+1] - zahyou[i])
    difference.sort()
    ans = sum(difference[:M-N])

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

x = sorted(X)
x_diff = [(x[m] - x[m - 1]) for m in range(1, M)]
x_diff.sort(reverse=True)

print((x[-1] - x[0]) - sum(x_diff[:N - 1]))

Submission status: Accepted

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

x = sorted(X)

diff = []
for n in range(1, M):
	diff += [abs(x[n] - x[n - 1])]
diff.sort(reverse=True)

print(abs(x[-1] - x[0]) - sum(diff[:N - 1]))

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

def s(generator, splitter, mapper):
    return [ mapper(s) for s in generator().split(splitter) ]

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

n,m = get_nums_l()
nums = get_nums_l()

nums.sort()
kaisa = [0] * (m-1)

for i in range(m-1):
    kaisa[i] = nums[i+1] - nums[i]

kaisa.sort(reverse=True)

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

Submission status: Accepted

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

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

X = sorted(X)
L = [ X[i] - X[i-1] for i in range(1, M)]
L = sorted(L)
#print(X)
#print(L)
 
print(sum(L[:M-N]))

Submission status: Accepted

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

L = []

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

L = sorted(L, reverse=True)

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

Submission status: Accepted

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

x.sort()

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

if m <= n:
    print(0)
else:
    length = x[m-1]-x[0]
    for i in range(n-1):
        length -= dist[i]
    print(length)

Submission status: Accepted

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

diffs = sorted([a - b for a, b in zip(X[1:], X[:])], reverse=True)
ans = sum(diffs[(N-1):])
print(ans)

Submission status: Accepted

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

if N >= M:
    print(0)
    exit()
    
r = abs(X[-1] - X[0])

difference = []

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

difference.sort()

while N-1 > 0:
    r -= difference[-1]
    del difference[-1]
    N -= 1
print(r)