Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import numpy as np
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])), dtype=np.int64)
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    dp = np.full((k+1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0

    for i in range(n):
        h = H[i]
        dh = d[h]
        dp2 = np.zeros((k+1, l), dtype=np.int64)
        dp2[0] = np.full(l, 10**13, dtype=np.int64)
        dp2[1:, :] = dp[:-1, :]
        temp = np.concatenate([(h-s)[:dh], np.zeros(l-dh, dtype=np.int64)])
        for j in range(k+1):
            dp2[j, dh] = min(dp2[j, dh], min(dp[j, :]+temp))
        dp = dp2
    print(np.min(dp))


main()

Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import numpy as np
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])), dtype=np.int64)
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    a = max(s)-s
    dp = np.full((1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0

    if k > 0:
        for i in range(n):
            h = H[i]
            dh = d[h]
            dp2 = np.zeros((min(i+2, k+1), l), dtype=np.int64)
            if i < k:
                s_plus_a = a+dp[:]
                min_s = dp[:]
            else:
                s_plus_a = a+dp[:-1]
                min_s = dp[:-1]
            for j in range(l-2, -1, -1):
                min_s[:, j] = np.minimum(min_s[:, j+1], min_s[:, j])
            for j in range(1, l):
                s_plus_a[:, j] = np.minimum(s_plus_a[:, j-1], s_plus_a[:, j])
            dp2[1:, :] = np.minimum(min_s, s_plus_a - a)
            dp2[0, :] = 10**13
            if i < k:
                for j in range(l):
                    dp2[:-1, dh] = np.minimum(dp2[:-1, dh],
                                              dp[:, j]+max(h-s[j], 0))
            else:
                for j in range(l):
                    dp2[:, dh] = np.minimum(
                        dp2[:, dh], dp[:, j]+max(h-s[j], 0))
            dp = dp2
    else:
        for h in H:
            dh = d[h]
            dp2 = np.full((1, l), 10**13, dtype=np.int64)
            for j in range(l):
                dp2[:, dh] = np.minimum(dp2[:, dh], dp[:, j]+max(h-s[j], 0))
            dp = dp2
    print(np.min(dp))


main()

Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[10**13]*l for _ in range(K+1)]
        t = [[i+j for i, j in zip(a, kk)] for kk in dp]
        min_s = [[dp[i][j] for j in range(l)] for i in range(K+1)]
        for i in range(K+1):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(min_s[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]
        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])
        for i in range(K+1):
            dp2[i][dh] = min(dp2[i][dh], min(
                [dp[i][j]+max(h-s[j], 0) for j in range(l)]))
        dp = dp2
    print(min([min(i) for i in dp]))


main()


Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import numpy as np
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])), dtype=np.int64)
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    a = max(s)-s
    dp = np.full((k+1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0

    if k > 0:
        for h in H:
            dh = d[h]
            dp2 = np.zeros((k+1, l), dtype=np.int64)
            s_plus_a = a+dp[:-1]
            min_s = dp[:-1]
            for j in range(l-2, -1, -1):
                min_s[:, j] = np.minimum(min_s[:, j+1], min_s[:, j])
            for j in range(1, l):
                s_plus_a[:, j] = np.minimum(s_plus_a[:, j-1], s_plus_a[:, j])
            dp2[1:, :] = np.minimum(min_s, s_plus_a - a)
            dp2[0, :] = 10**13
            for j in range(l):
                dp2[:, dh] = np.minimum(dp2[:, dh], dp[:, j]+max(h-s[j], 0))
            dp = dp2
    else:
        for h in H:
            dh = d[h]
            dp2 = np.full((1, l), 10**13, dtype=np.int64)
            for j in range(l):
                dp2[:, dh] = np.minimum(dp2[:, dh], dp[:, j]+max(h-s[j], 0))
            dp = dp2
    print(np.min(dp))


main()


Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    import numpy as np
    n, k = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])), dtype=np.int64)
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    a = max(s)-s
    dp = np.full((k+1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0
    for h in H:
        dh = d[h]
        dp2 = np.full((k+1, l), 10**13, dtype=np.int64)
        if k > 0:
            t = np.zeros((k, l), dtype=np.int64)
            s_plus_a = a+dp
            min_s = np.array([[j for j in i] for i in dp[:-1]], dtype=np.int64)
            for j in range(l-2, -1, -1):
                min_s[:, j] = np.minimum(min_s[:, j+1], min_s[:, j])
            for j in range(1, l):
                s_plus_a[:, j] = np.minimum(s_plus_a[:, j-1], s_plus_a[:, j])
            t = s_plus_a[:-1] - a
            dp2[1:, :] = np.minimum(min_s, t)
        for j in range(l):
            dp2[:, dh] = np.minimum(dp2[:, dh], dp[:, j]+max(h-s[j], 0))
        dp = dp2
    print(np.min(dp))


main()

Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Buggy python submission (verdict: Runtime Error):
def main():
    import numpy as np
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = np.array(sorted(set(H+[0])))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    a = max(s)-s
    dp = np.full((K+1, l), 10**13, dtype=np.int64)
    dp[0, 0] = 0
    for h in H:
        dh = d[h]
        dp2 = np.full((K+1, l), 10**13, dtype=np.int64)
        t = np.zeros((K, l), dtype=np.int64)
        s_plus_a = a+dp
        min_s = np.array([[j for j in i] for i in dp[:-1]], dtype=np.int64)
        for j in range(l-2, -1, -1):
            min_s[:, j] = np.minimum(min_s[:, j+1], min_s[:, j])
        for j in range(1, l):
            s_plus_a[:, j] = np.minimum(s_plus_a[:, j-1], s_plus_a[:, j])
        t = s_plus_a[:-1] - a
        dp2[1:, :] = np.minimum(min_s, t)
        for j in range(l):
            dp2[:, dh] = np.minimum(dp2[:, dh], dp[:, j]+max(h-s[j], 0))
        dp = dp2
    print(np.min(dp))


main()

Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[10**13]*l for _ in range(K+1)]
        t = [[0]*l for _ in range(K+1)]
        s_plus_a = [[i+j for i, j in zip(a, kk)] for kk in dp]
        min_s = [[dp[i][j] for j in range(l)] for i in range(K+1)]
        for i in range(K+1):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(min_s[i][j+1], min_s[i][j])
            for j in range(1, l):
                s_plus_a[i][j] = min(s_plus_a[i][j-1], s_plus_a[i][j])
            for j in range(l):
                t[i][j] = s_plus_a[i][j]-a[j]
        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])
        for i in range(K+1):
            for j in range(l):
                dp2[i][dh] = min(dp2[i][dh], dp[i][j]+max(h-s[j], 0))
        dp = dp2
    print(min([min(i) for i in dp]))


main()


Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[10**13]*l for _ in range(K+1)]
        t = [[0]*l for _ in range(K+1)]
        s_plus_a = [[i+j for i, j in zip(a, kk)] for kk in dp]
        min_s = [[dp[i][j] for j in range(l)] for i in range(K+1)]
        for i in range(K+1):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(min_s[i][j+1], min_s[i][j])
            for j in range(1, l):
                s_plus_a[i][j] = min(s_plus_a[i][j-1], s_plus_a[i][j])
            for j in range(l):
                t[i][j] = s_plus_a[i][j]-a[j]
        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])
        for i in range(K+1):
            for j in range(l):
                dp2[i][dh] = min(dp2[i][dh], dp[i][j]+max(h-s[j], 0))
        dp = dp2
    print(min([min(i) for i in dp]))


main()


Fixed submission:
def main():
    n, K = map(int, input().split())
    H = list(map(int, input().split()))
    s = sorted(set(H+[0]))
    d = {i: j for j, i in enumerate(s)}
    l = len(s)
    m = max(s)
    a = [m-i for i in s]
    dp = [[10**13]*l for _ in range(K+1)]
    dp[0][0] = 0
    for h in H:
        dh = d[h]
        dp2 = [[0]*l for _ in range(K+1)]
        dp2[0] = [10**13]*l
        t = [[0]*l for _ in range(K)]
        for i in range(K):
            for j in range(l):
                t[i][j] = dp[i][j]+a[j]
        min_s = [[10**13]*l for i in range(K+1)]

        for i in range(K):
            for j in range(l-2, -1, -1):
                min_s[i][j] = min(dp[i][j+1], min_s[i][j])
            for j in range(1, l):
                t[i][j] = min(t[i][j-1], t[i][j])
            for j in range(l):
                t[i][j] = t[i][j]-a[j]

        for i in range(K):
            for j in range(l):
                dp2[i+1][j] = min(min_s[i][j], t[i][j])

        for i in range(K+1):
            temp = 10**13
            for j in range(l):
                temp = min(temp, dp[i][j]+max(h-s[j], 0))
            dp2[i][dh] = min(dp2[i][dh], temp)
        dp = dp2
    print(min([min(i) for i in dp]))


main()