Problem: 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.

Submission attempts (in order):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
import numpy as np
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    N, M = LI()
    X = LI()
    #  print(N, M, X)

    X.sort()
    #  print(X)

    if N >= M:
        print(0)
        return
    if N == 1:
        
        print(X[-1] - X[0])
        return

    N_position_list = []
    
    X_diff = [X[i+1] - X[i] for i in range(len(X)-1)]
    order_idx = np.argsort(X_diff)
    #  print(X_diff)
    
    
    count = 0
    torn_point = []
    
    while count < N - 1:
        max_idx = max(order_idx)
        order_idx = [i for i in order_idx if i != max_idx]
        torn_point.append(max_idx)
        X_diff[max_idx] = -10**5-1
        count += 1

   
    
    
    
    torn_list = []
    for i in range(len(torn_point)):
        if i == 0:
            torn_list.append(X[0:torn_point[i]+1])
        else:
            torn_list.append(X[torn_point[i-1]+1:torn_point[i]+1])
    else:
        torn_list.append(X[torn_point[-1]+1:])

    

    move_count = 0
    for l in torn_list:
        if len(l) >= 2:
            
            move_count += l[-1] - l[0]

    print(move_count)


main()


import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

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


Verdicts: Wrong Answer

Accepted