oj.uz

Submission #559828

# Submission time Handle Problem Language Result Execution time Memory
559828 2022-05-10T17:30:22 Z kuanc Stove (JOI18_stove) PyPy 3
100 / 100
 159 ms 27272 KB 
# ======== 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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