Submission #67544749

---

Source Code Expand

import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ria1(): return list(map(lambda x: int(x)-1, sys.stdin.readline().split()))
def ria2d(n): return [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
def rg(n, m, directed=False):
    g = [[] for _ in range(n)]
    for _ in range(m):
        u, v = ria1()
        g[u].append(v)
        if not directed:
            g[v].append(u)
    return g
def ws(s): sys.stdout.write(s); sys.stdout.write('\n')
def wi(n): sys.stdout.write(str(n)); sys.stdout.write('\n')
def wia(a, sep=' '): sys.stdout.write(sep.join([str(x) for x in a])); sys.stdout.write('\n')
def wia1(a, sep=' '): sys.stdout.write(sep.join([str(x+1) for x in a])); sys.stdout.write('\n')


def solve(n, m, x):
    x.sort()
    r = x[-1] - x[0]

    if m == 1:
        return r

    d = [x[i] - x[i-1] for i in range(1, n)]
    d.sort(reverse=True)

    s = sum(d[:m-1])

    def check(y):
        need = r - y
        return s >= need

    lo, hi = -1, r
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid
        else:
            lo = mid
    return hi

def main():
    n, m = ria()
    x = ria()
    wi(solve(n, m, x))


if __name__ == '__main__':
    main()

Submission Info

Judge Result