Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    i = N - 1
    j = 0
    big = A[i]
    small = A[j]
    i -= 1
    j += 1
    res = []
    while i <= j:
        if i == j:
            res.append((small, A[i]))
            small -= A[i]
            break
        res.append((big, A[j]))
        big -= A[j]
        res.append((small, A[i]))
        small -= A[i]
        i -= 1
        j += 1

    print(big - small)
    for x, y in res:
        print(x, y)
    print(big, small)


solve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    big = A[-1]
    small = A[0]
    res = []
    for i in range(1, N - 1):
        if A[i] > 0:
            res.append((small, A[i]))
            small -= A[i]
        else:
            res.append((big, A[i]))
            big -= A[i]
    res.append((big, small))
    print(big - small)
    for x, y in res:
        print(x, y)


solve()

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    i = N - 1
    j = 0
    big = A[i]
    small = A[j]
    i -= 1
    j += 1
    res = []
    while i <= j:
        if i == j:
            small -= A[i]
            res.append((small, A[i]))
            break
        big -= A[j]
        res.append((big, A[j]))
        small -= A[i]
        res.append((small, A[i]))
        i -= 1
        j += 1

    print(big - small)
    for x, y in res:
        print(x, y)


solve()


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

N = ini()
A = inl()
A.sort()


def solve():
    big = A[-1]
    small = A[0]
    res = []
    for i in range(1, N - 1):
        if A[i] > 0:
            res.append((small, A[i]))
            small -= A[i]
        else:
            res.append((big, A[i]))
            big -= A[i]
    res.append((big, small))
    print(big - small)
    for x, y in res:
        print(x, y)


solve()
Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[None]*W for _ in range(H)]
horiv = [[] for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '.':
            horiz[i][j] = len(horiv[i])
        else:
            horiv[i].append(j - cur)
            cur = j + 1
    horiv[i].append(W-cur)

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiv[r][horiz[r][c]])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)

Fixed submission:
H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[None]*W for _ in range(H)]
horiv = [[] for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '.':
            horiz[i][j] = len(horiv[i])
        else:
            horiv[i].append(j - cur)
            cur = j + 1
    horiv[i].append(W-cur)

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiv[r][horiz[r][c]])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)

Buggy python submission (verdict: Time Limit Exceeded):
H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[0]*W for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '#':
            for k in range(cur, j):
                horiz[i][k] = j-cur
            cur = j+1
    for k in range(cur, W):
        horiz[i][k] = W-cur

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiz[r][c])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)

Fixed submission:
H,W = map(int, input().split())
grid = []
for i in range(H):
    grid.append(input())
horiz = [[None]*W for _ in range(H)]
horiv = [[] for _ in range(H)]
for i in range(H):
    cur = 0
    for j in range(W):
        if grid[i][j] == '.':
            horiz[i][j] = len(horiv[i])
        else:
            horiv[i].append(j - cur)
            cur = j + 1
    horiv[i].append(W-cur)

maxv = 0
for c in range(W):
    cur = 0
    besth = 0
    for r in range(H):
        if grid[r][c] == '.':
            besth = max(besth, horiv[r][horiz[r][c]])
        else:
            maxv = max(maxv, r-cur + besth - 1)
            cur = r+1
            besth = 0
    maxv = max(maxv, H-cur + besth - 1)

print(maxv)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import heapq

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print("\033[33m", *a, "\033[0m", **dict(file=sys.stderr, **kw))

n, m = inm()
a = inl()


def solve():
    heapq.heapify(a)
    for i in range(m):
        b, c = inm()
        for j in range(b):
            if a[0] >= c:
                break
            heapq.heappush(a, c)
            heapq.heappop(a)
    return sum(a)


print(solve())


Fixed submission:
n,m = map(int,input().split())
a = list(map(int,input().split()))
assert len(a) == n
cb = [None]*m
for i in range(m):
    b, c = map(int,input().split())
    cb[i] = (c,b)
a.sort(reverse=True)
cb.sort(reverse=True)

def solve():
    ai = 0
    ci = 0
    res = [None]*n
    for i in range(n):
        if ci >= len(cb):
            cx, bx = -100, 1
        else:
            cx, bx = cb[ci]
        ax = a[ai]
        if ax >= cx:
            res[i] = ax
            ai += 1
        else:
            res[i] = cx
            cb[ci] = (cx, bx-1)
            if bx-1 <= 0:
                ci += 1
    return sum(res)

print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N = int(input())
en = [[] for _ in range(N)]
on = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2:
        on[u - 1].append(v - 1)
        on[v - 1].append(u - 1)
    else:
        en[u - 1].append(v - 1)
        en[v - 1].append(u - 1)

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N = int(input())
en = [[] for _ in range(N)]
on = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2:
        on[u - 1].append(v - 1)
        on[v - 1].append(u - 1)
    else:
        en[u - 1].append(v - 1)
        en[v - 1].append(u - 1)

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")

Buggy python submission (verdict: Runtime Error):
N = int(input())
en = [[] for _ in range(N)]
on = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2:
        on[u - 1].append(v - 1)
        on[v - 1].append(u - 1)
    else:
        en[u - 1].append(v - 1)
        en[v - 1].append(u - 1)

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

N = int(input())
en = [[] for _ in range(N)]
on = [[] for _ in range(N)]
for i in range(N - 1):
    u, v, w = map(int, input().split())
    if w % 2:
        on[u - 1].append(v - 1)
        on[v - 1].append(u - 1)
    else:
        en[u - 1].append(v - 1)
        en[v - 1].append(u - 1)

color = [None] * N


def dfs(node, parent, col):
    if color[node] is not None:
        return
    color[node] = col
    for k in en[node]:
        if k != parent:
            dfs(k, node, col)
    for k in on[node]:
        if k != parent:
            dfs(k, node, (col + 1) % 2)


dfs(0, -1, 0)
print(*color, sep="\n")
Buggy python submission (verdict: Runtime Error):
import sys
N = int(sys.stdin.readline())
ss = []
for i in range(N):
    ss.append(sys.stdin.readline().rstrip())

incount = 0
has_ba = 0
has_b = 0
has_a = 0
for s in ss:
    incount += s.count('AB')
    if s[0] == 'B' and s[-1] == 'A':
        has_ba += 1
    elif s[0] == 'B':
        has_b += 1
    elif s[-1] == 'A':
        has_a += 1

res = incount
if has_a:
    res += has_ba
elif has_ba:
    has_a += 1
    has_ba -= 1
    res += has_ba
res += min(has_a, has_b)

print(res)


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, K = nm()


def solve():
    return N - K + 1


if __name__ == "__main__":
    print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import collections

input = sys.stdin.readline

H, W = map(int, input().split())
q = collections.deque()
grid = []
for i in range(H):
    grid.append(list(input().strip()))
    for j in range(W):
        if grid[i][j] == "#":
            q.append((i, j, 0))

maxc = 0
while q:
    i, j, c = q.popleft()
    if maxc < c:
        maxc = c
    if i > 0 and grid[i - 1][j] == ".":
        q.append((i - 1, j, c + 1))
        grid[i - 1][j] = "#"
    if i < H - 1 and grid[i + 1][j] == ".":
        q.append((i + 1, j, c + 1))
        grid[i + 1][j] = "#"
    if j > 0 and grid[i][j - 1] == ".":
        q.append((i, j - 1, c + 1))
        grid[i][j - 1] = "#"
    if j < W - 1 and grid[i][j + 1] == ".":
        q.append((i, j + 1, c + 1))
        grid[i][j + 1] = "#"

print(maxc)


Fixed submission:
import sys
import collections

input = sys.stdin.readline

H, W = map(int, input().split())
q = collections.deque()
grid = []
for i in range(H):
    grid.append(list(input().strip()))
    for j in range(W):
        if grid[i][j] == "#":
            q.append((i, j, 0))

maxc = 0
while q:
    i, j, c = q.popleft()
    if maxc < c:
        maxc = c
    if i > 0 and grid[i - 1][j] == ".":
        q.append((i - 1, j, c + 1))
        grid[i - 1][j] = "#"
    if i < H - 1 and grid[i + 1][j] == ".":
        q.append((i + 1, j, c + 1))
        grid[i + 1][j] = "#"
    if j > 0 and grid[i][j - 1] == ".":
        q.append((i, j - 1, c + 1))
        grid[i][j - 1] = "#"
    if j < W - 1 and grid[i][j + 1] == ".":
        q.append((i, j + 1, c + 1))
        grid[i][j + 1] = "#"

print(maxc)
Buggy python submission (verdict: Runtime Error):
import sys

# import numpy as np


def main():
    f = sys.stdin.buffer
    N, K = map(int, f.readline().split())
    H = list(map(int, f.readline().split()))
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(
            dp[i - k - 1] + abs(H[i] - H[i - k - 1]) for k in range(K) if i - k - 1 >= 0
        )
    print(dp[-1])


if __name__ == "__main__":
    main()


Fixed submission:
import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
dp = [0]*n
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
import sys
import numpy as np


def main():
    f = sys.stdin.buffer
    N, K = map(int, f.readline().split())
    H = list(map(int, f.readline().split()))
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(
            dp[i - k - 1] + abs(H[i] - H[i - k - 1]) for k in range(K) if i - k - 1 >= 0
        )
    print(dp[-1])


if __name__ == "__main__":
    main()


Fixed submission:
import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
dp = [0]*n
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])

Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
h = np.array(h)
dp = np.zeros(n, int)
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])


Fixed submission:
import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
dp = [0]*n
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
h = np.array(h)
dp = np.zeros(n, int)
dp[1] = abs(h[1] - h[0])
for i in range(n - 1):
    np.minimum(
        dp[1:-1] + np.abs(h[2:] - h[1:-1]), dp[:-2] + np.abs(h[2:] - h[:-2]), out=dp[2:]
    )
print(dp[-1])


Fixed submission:
import sys
f = sys.stdin
n = int(f.readline())
h = list(map(int, f.readline().split()))
dp = [0]*n
dp[1] = abs(h[1] - h[0])
for i in range(2, n):
    dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [1 << 62] * N
dp[0] = 0
for i in range(1, N):
    for j in range(i, min(i + K, N)):
        cost = abs(H[i - 1] - H[j])
        dp[j] = min(dp[j], dp[i - 1] + cost)
print(dp[-1])


Fixed submission:
import sys

# import numpy as np


def main():
    f = sys.stdin.buffer
    N, K = map(int, f.readline().split())
    H = list(map(int, f.readline().split()))
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(
            dp[i - k - 1] + abs(H[i] - H[i - k - 1]) for k in range(K) if i - k - 1 >= 0
        )
    print(dp[-1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
H = list(map(int, input().split()))
dp = [1 << 62] * N
dp[0] = 0
for i in range(1, N):
    for j in range(i, min(i + 1 + K, N)):
        cost = abs(H[i - 1] - H[i + j])
        dp[i + j] = min(dp[i + j], dp[i - 1] + cost)
print(dp[-1])


Fixed submission:
import sys

# import numpy as np


def main():
    f = sys.stdin.buffer
    N, K = map(int, f.readline().split())
    H = list(map(int, f.readline().split()))
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(
            dp[i - k - 1] + abs(H[i] - H[i - k - 1]) for k in range(K) if i - k - 1 >= 0
        )
    print(dp[-1])


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np


def main():
    f = sys.stdin.buffer
    N, K = map(int, f.readline().split())
    H = list(map(int, f.readline().split()))
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(
            dp[i - k - 1] + abs(H[i] - H[i - k - 1]) for k in range(K) if i - k - 1 >= 0
        )
    print(dp[-1])


if __name__ == "__main__":
    main()


Fixed submission:
import sys

# import numpy as np


def main():
    f = sys.stdin.buffer
    N, K = map(int, f.readline().split())
    H = list(map(int, f.readline().split()))
    dp = [0] * N
    for i in range(1, N):
        dp[i] = min(
            dp[i - k - 1] + abs(H[i] - H[i - k - 1]) for k in range(K) if i - k - 1 >= 0
        )
    print(dp[-1])


if __name__ == "__main__":
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))


def solve():
    dp = [0] * (W + 1)
    w0, v0 = things[0]
    for i in range(w0, W + 1):
        dp[i] = v0
    for i in range(1, N):
        dn = list(dp)
        weight, value = things[i]
        for j in range(weight, W + 1):
            dn[j] = max(dn[j], dp[j - weight] + value)
        dp = dn
    return dp[W]


if __name__ == "__main__":
    print(solve())


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))


def solve():
    dp = [0] * (W + 1)
    w0, v0 = things[0]
    for i in range(w0, W + 1):
        dp[i] = v0
    for i in range(1, N):
        dn = list(dp)
        weight, value = things[i]
        for j in range(weight, W + 1):
            dn[j] = max(dn[j], dp[j - weight] + value)
        dp = dn
    return dp[W]


if __name__ == "__main__":
    print(solve())

Buggy python submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))


def solve():
    dp = [0] * (W + 1)
    w0, v0 = things[0]
    for i in range(w0, W + 1):
        dp[i] = v0
    for i in range(1, N):
        dn = dp.copy()
        weight, value = things[i]
        for j in range(weight, W + 1):
            dn[j] = max(dn[j], dp[j - weight] + value)
        dp = dn
    return dp[W]


if __name__ == "__main__":
    print(solve())


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))


def solve():
    dp = [0] * (W + 1)
    w0, v0 = things[0]
    for i in range(w0, W + 1):
        dp[i] = v0
    for i in range(1, N):
        dn = list(dp)
        weight, value = things[i]
        for j in range(weight, W + 1):
            dn[j] = max(dn[j], dp[j - weight] + value)
        dp = dn
    return dp[W]


if __name__ == "__main__":
    print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
vsum = 0
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))
    vsum += value


INF = 1 << 62


def solve():
    dp = [INF] * (vsum + 1)
    w0, v0 = things[0]
    dp[0] = 0
    dp[v0] = w0
    for i in range(1, N):
        dn = list(dp)
        w, v = things[i]
        for j in range(vsum - v + 1):
            w2 = dp[j] + w
            if j + v <= vsum and w2 <= W:
                dn[j + v] = min(dn[j + v], w2)
        dp = dn
    for i in range(vsum, -1, -1):
        w = dp[i]
        if w <= W:
            return i
    return 0  # nothing is available


if __name__ == "__main__":
    print(solve())


Fixed submission:
import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
vsum = 0
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))
    vsum += value


INF = 1 << 62


def solve():
    dp = [INF] * (vsum + 1)
    w0, v0 = things[0]
    dp[0] = 0
    dp[v0] = w0
    for i in range(1, N):
        dn = list(dp)
        w, v = things[i]
        for j in range(vsum - v + 1):
            w2 = dp[j] + w
            if j + v <= vsum and w2 <= W:
                dn[j + v] = min(dn[j + v], w2)
        dp = dn
    for i in range(vsum, -1, -1):
        w = dp[i]
        if w <= W:
            return i
    return 0  # nothing is available


if __name__ == "__main__":
    print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import copy
import sys

MOD = 1000000007  # type: int


def debug(s):
    print(s)


def solve(N: int, K: int, a: "List[int]"):
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        ai = a[i - 1]
        dp[i][0] = 1
        for k in range(1, K + 1):
            c = dp[i - 1][k] + dp[i][k - 1]
            if k - ai - 1 >= 0:
                c -= dp[i - 1][k - ai - 1]
            dp[i][k] = c % MOD
            # debug(f"{i} kids share {k} candies: => {dp[i][k]}")
    return dp[N][K]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, K, a))


if __name__ == "__main__":
    main()


Fixed submission:
#!/usr/bin/env python3
import copy
import sys

MOD = 1000000007  # type: int


def debug(s):
    print(s)


def solve(N: int, K: int, a: "List[int]"):
    dp = [[0] * (K + 1) for _ in range(N + 1)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        ai = a[i - 1]
        dp[i][0] = 1
        for k in range(1, K + 1):
            c = dp[i - 1][k] + dp[i][k - 1]
            if k - ai - 1 >= 0:
                c -= dp[i - 1][k - ai - 1]
            dp[i][k] = c % MOD
            # debug(f"{i} kids share {k} candies: => {dp[i][k]}")
    return dp[N][K]


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, K, a))


if __name__ == "__main__":
    main()