Submission #559828

#	Time	Username	Problem	Language	Result	Execution time	Memory
559828		kuanc	Stove (JOI18_stove)	Pypy 3	100 / 100	159 ms	27272 KiB

stove

# ======== author: kuanc (@kuantweets) | created: 05/11/22 01:25:10 ======== #
from sys            import setrecursionlimit, stdin, stdout, stderr
from bisect         import bisect_left, bisect_right
from collections    import defaultdict, deque, Counter
from itertools      import accumulate, combinations, permutations, product
from functools      import lru_cache, cmp_to_key, reduce
from heapq          import heapify, heappush, heappop, heappushpop, heapreplace
# from pypyjit        import set_param
# set_param("max_unroll_recursion=-1")
# setrecursionlimit(300005)
INF   = 1 << 60
MOD   = 998244353 + 1755654
input = lambda: stdin.readline().rstrip("\r\n")
dbg   = lambda *A, **M: stderr.write("\033[91m" + \
        M.get("sep", " ").join(map(str, A)) + M.get("end", "\n") + "\033[0m")
# ============================ START OF MY CODE ============================ #

def solve(_tc):
    N, K = map(int, input().split())
    K -= 1

    pq = []
    prev = 0
    first = INF
    for _ in range(N):
        x = int(input())
        if prev:
            heappush(pq, -(x - prev))
        first = min(first, x)
        prev = x

    ans = prev - first + 1
    while pq and K:
        x = -heappop(pq) - 1
        ans -= x
        K -= 1

    print(ans)


if __name__ == "__main__":
    # _tcs = int(input())
    for _tc in range(1, vars().get("_tcs", 1) + 1):
        dbg("=== Case {} ===".format(str(_tc).rjust(2)))
        solve(_tc)

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 50 / 50