답안 #559828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
559828	2022-05-10T17:30:22 Z	kuanc	Stove (JOI18_stove)	PyPy 3	100 / 100	159 ms	27272 KB

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.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	18812 KB	Output is correct
2	Correct	47 ms	18880 KB	Output is correct
3	Correct	44 ms	18772 KB	Output is correct
4	Correct	44 ms	18808 KB	Output is correct
5	Correct	47 ms	18804 KB	Output is correct
6	Correct	43 ms	18748 KB	Output is correct
7	Correct	45 ms	18860 KB	Output is correct
8	Correct	48 ms	18816 KB	Output is correct
9	Correct	45 ms	18860 KB	Output is correct

Subtask #2

30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	18812 KB	Output is correct
2	Correct	47 ms	18880 KB	Output is correct
3	Correct	44 ms	18772 KB	Output is correct
4	Correct	44 ms	18808 KB	Output is correct
5	Correct	47 ms	18804 KB	Output is correct
6	Correct	43 ms	18748 KB	Output is correct
7	Correct	45 ms	18860 KB	Output is correct
8	Correct	48 ms	18816 KB	Output is correct
9	Correct	45 ms	18860 KB	Output is correct
10	Correct	71 ms	20904 KB	Output is correct
11	Correct	68 ms	21344 KB	Output is correct
12	Correct	80 ms	21776 KB	Output is correct
13	Correct	88 ms	22500 KB	Output is correct
14	Correct	88 ms	22584 KB	Output is correct
15	Correct	92 ms	22716 KB	Output is correct

Subtask #3

50.0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	46 ms	18812 KB	Output is correct
2	Correct	47 ms	18880 KB	Output is correct
3	Correct	44 ms	18772 KB	Output is correct
4	Correct	44 ms	18808 KB	Output is correct
5	Correct	47 ms	18804 KB	Output is correct
6	Correct	43 ms	18748 KB	Output is correct
7	Correct	45 ms	18860 KB	Output is correct
8	Correct	48 ms	18816 KB	Output is correct
9	Correct	45 ms	18860 KB	Output is correct
10	Correct	71 ms	20904 KB	Output is correct
11	Correct	68 ms	21344 KB	Output is correct
12	Correct	80 ms	21776 KB	Output is correct
13	Correct	88 ms	22500 KB	Output is correct
14	Correct	88 ms	22584 KB	Output is correct
15	Correct	92 ms	22716 KB	Output is correct
16	Correct	96 ms	26532 KB	Output is correct
17	Correct	96 ms	26624 KB	Output is correct
18	Correct	108 ms	26432 KB	Output is correct
19	Correct	116 ms	26212 KB	Output is correct
20	Correct	144 ms	26832 KB	Output is correct
21	Correct	139 ms	26556 KB	Output is correct
22	Correct	144 ms	26896 KB	Output is correct
23	Correct	143 ms	27272 KB	Output is correct
24	Correct	159 ms	27216 KB	Output is correct