Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(input())
point = []
for i in range(n):
    x_, y_ = map(int, input().split())
    point.append([x_, y_])

point.sort()
ans = 0
x = point[:][0]
y = point[:][1]
for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[l] - x[k] == p) and (y[l] - y[k] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)


Fixed submission:
n = int(input())
point = []
for i in range(n):
    x_, y_ = map(int, input().split())
    point.append([x_, y_])

point.sort(key=lambda x: x[1])
point.sort(key=lambda x: x[0])
ans = 0
x = []
y = []
for i in range(n):
    x.append(point[i][0])
    y.append(point[i][1])

for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[l] - x[k] == p) and (y[l] - y[k] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)

Buggy python submission (verdict: Runtime Error):
n = int(input())
point = []
for i in range(n):
    x_, y_ = map(int, input().split())
    point.append((x_, y_))

point.sort(key=lambda x: x[0])
ans = 0
x = point[:][0]
y = point[:][1]
for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[l] - x[k] == p) and (y[l] - y[k] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)


Fixed submission:
n = int(input())
point = []
for i in range(n):
    x_, y_ = map(int, input().split())
    point.append([x_, y_])

point.sort(key=lambda x: x[1])
point.sort(key=lambda x: x[0])
ans = 0
x = []
y = []
for i in range(n):
    x.append(point[i][0])
    y.append(point[i][1])

for i in range(n):
    for j in range(i+1, n):
        count = 0
        p = x[j] - x[i]
        q = y[j] - y[i]
        for k in range(n):
            for l in range(k+1, n):
                if (x[l] - x[k] == p) and (y[l] - y[k] == q):
                    count += 1
        ans = max(ans, count)

print(n - ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

a.sort()
if a[0] > 0:
    m = sum(a[1:]) - a[0]
    print(m)
    tmp = a[0]
    for i in range(1, n-1):
        print(tmp, a[i])
        tmp -= a[i]
    print(a[n-1], tmp)
elif a[-1] < 0:
    m = -sum(a[:-1]) + a[-1]
    print(m)
    tmp = a[n-1]
    for i in range(0, n-1, -1):
        print(tmp, a[i])
        tmp -= a[i]
else:
    m = 0
    pos = []
    neg = []
    for ai in a:
        m += abs(ai)
        if ai >= 0:
            pos.append(ai)
        else:
            neg.append(ai)
    print(m)
    tmp = 0
    ni = 0
    pi = 0

    if len(pos) > 1:
        print(neg[ni], pos[pi])  # pos > 1
        tmp = neg[ni] - pos[pi]
        ni += 1
        pi += 1

        while pi < len(pos) - 1:
            print(tmp, pos[pi])
            tmp = tmp - pos[pi]
            pi += 1
        print(pos[pi], tmp)
        tmp = pos[pi] - tmp
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg
            ni += 1
    else:
        print(pos[pi] - neg[ni])
        tmp = pos[pi] - neg[ni]
        ni += 1
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg
            ni += 1





Fixed submission:
n = int(input())
a = list(map(int, input().split()))

a.sort()
if a[0] >= 0:
    m = sum(a[1:]) - a[0]
    print(m)
    tmp = a[0]
    for i in range(1, n-1):
        print(tmp, a[i])
        tmp -= a[i]
    print(a[n-1], tmp)
elif a[-1] <= 0:
    m = -sum(a[:-1]) + a[-1]
    print(m)
    tmp = a[n-1]
    for i in range(n-1):
        print(tmp, a[i])
        tmp -= a[i]
else:
    m = 0
    pos = []
    neg = []
    for ai in a:
        m += abs(ai)
        if ai >= 0:
            pos.append(ai)
        else:
            neg.append(ai)
    print(m)
    tmp = 0
    ni = 0
    pi = 0

    if len(pos) > 1:
        print(neg[ni], pos[pi])
        tmp = neg[ni] - pos[pi]
        ni += 1
        pi += 1

        while pi < len(pos) - 1:
            print(tmp, pos[pi])
            tmp = tmp - pos[pi]
            pi += 1
        print(pos[pi], tmp)
        tmp = pos[pi] - tmp
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg[ni]
            ni += 1
    else:
        print(pos[pi], neg[ni])
        tmp = pos[pi] - neg[ni]
        ni += 1
        while ni < len(neg):
            print(tmp, neg[ni])
            tmp -= neg[ni]
            ni += 1
Buggy python submission (verdict: Time Limit Exceeded):
import bisect
n, q = map(int, input().split())

ran = []
for i in range(n):
    s, t, x = map(int, input().split())
    ran.append((s-x, t-x-1, x))
ran.sort(key=lambda a: a[2])

qu = []
convert = {}
for i in range(q):
    que = int(input())
    convert[que] = i
    qu.append(que)
qu.sort()

memo = [-1] * q

ans = [-1] * q

for i in range(n):
    x = ran[i][2]
    l = ran[i][0]
    r = ran[i][1]
    ql = bisect.bisect_left(qu, l)
    qr = bisect.bisect_right(qu, r)
    if ql >= qr:
        continue
    while ql < qr:
        if memo[ql] >= 0:
            ql = memo[ql]
        else:
            memo[ql] = qr
            ans[convert[qu[ql]]] = x
            ql += 1

for i in ans:
    print(i)

Fixed submission:
import sys
input = sys.stdin.readline
import bisect
n, q = map(int, input().split())

ran = []
for i in range(n):
    s, t, x = map(int, input().split())
    ran.append((s-x, t-x-1, x))
ran.sort(key=lambda a: a[2])

qu = []
convert = {}
for i in range(q):
    que = int(input())
    convert[que] = i
    qu.append(que)
qu.sort()

memo = [-1] * q

ans = [-1] * q

for i in range(n):
    x = ran[i][2]
    l = ran[i][0]
    r = ran[i][1]
    ql = bisect.bisect_left(qu, l)
    qr = bisect.bisect_right(qu, r)
    if ql >= qr:
        continue
    while ql < qr:
        if memo[ql] >= 0:
            ql = memo[ql]
        else:
            memo[ql] = qr
            ans[convert[qu[ql]]] = x
            ql += 1

for i in ans:
    print(i)
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
b_c = [list(map(int, input().split())) for _ in range(m)]
b_c.sort(key=lambda x: x[1], reverse=True)

j = 0
for i in range(m):
    b = b_c[i][0]
    c = b_c[i][1]
    for _ in range(b):
        if a[j] < c:
            a[j] = c
            j += 1
        else:
            break

print(sum(a))

Fixed submission:
n, m = map(int, input().split())
a = list(map(int, input().split()))

a.sort()
b_c = [list(map(int, input().split())) for _ in range(m)]
b_c.sort(key=lambda x: x[1], reverse=True)

j = 0
for i in range(m):
    b = b_c[i][0]
    c = b_c[i][1]
    for _ in range(b):
        if j >= n:
            print(sum(a))
            exit()
        if a[j] < c:
            a[j] = c
            j += 1
        else:
            break

print(sum(a))
Buggy python submission (verdict: Time Limit Exceeded):
R, G, B, N = map(int, input().split())

count = 0

for r in range(N//R + 1):
    for g in range(N//G + 1):
        if 0 <= (N - R * r - G * g) and (N - R * r - G * g) % B == 0:
            count += 1

print(count)

Fixed submission:
R, G, B, N = map(int, input().split())

count = 0

for r in range(N//R + 1):
    for g in range(N//G + 1):
        if 0 <= (N - R * r - G * g) and (N - R * r - G * g) % B == 0:
            count += 1

print(count)
Buggy python submission (verdict: Runtime Error):
n = int(input())

ans = 0


i = 1
while i * i <= n:
    if n % i == 0:
        if n // (i-1) == n % (i-1):
            ans += n // i - 1
    i += 1

print(ans)

Fixed submission:
n = int(input())

ans = 0


i = 1
while i * i < n:
    if n % i == 0:
        m = n // i - 1
        if m > i:
            ans += m
    i += 1

print(ans)
Buggy python submission (verdict: Runtime Error):
num = [int(input()) for _ in range(5)]

ans = 0
flag = 0
for i in num:
    if i % 10 == 0:
        ans += i
    else:
        ans += i // 10 * 10 + 10
        flag = 1

if flag:
    ma = 0
    for i in num:
        if i % 10 == 0:
            continue
        ma = max(ma, 10 - i % 10)

print(ans - ma)



Fixed submission:
num = [int(input()) for _ in range(5)]

ans = 0
flag = 0
for i in num:
    if i % 10 == 0:
        ans += i
    else:
        ans += i // 10 * 10 + 10
        flag = 1

ma = 0
if flag:
    for i in num:
        if i % 10 == 0:
            continue
        ma = max(ma, 10 - i % 10)

print(ans - ma)
Buggy python submission (verdict: Time Limit Exceeded):
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
for ai in a:
    for bi in b:
        ab.append(ai + bi)
ab.sort(reverse=True)
if k < len(ab):
    ab = ab[:k]

ans = []
for abi in ab:
    for ci in c:
        ans.append(abi + ci)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])


Fixed submission:
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
for ai in a:
    for bi in b:
        ab.append(ai + bi)
ab.sort(reverse=True)
if k < len(ab):
    ab = ab[:k]

ans = []
for abi in ab:
    for ci in c:
        ans.append(abi + ci)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])

Buggy python submission (verdict: Runtime Error):
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
b.sort()
c.sort()

if x * y * z <= 3000:
    ans = []
    for ai in a:
        for bi in b:
            for ci in c:
                ans.append(ai + bi+ ci)
    ans.sort(reverse=True)
    for i in range(k):
        print(ans[i])
else:
    ia = 0
    ib = 0
    ic = 0
    len_a = len(a)
    len_b = len(b)
    len_c = len(c)

    while (ia+1) * (ib+1) * (ic+1) < 3000:
        if ia + 1 == len_a:
            diff_a = float('inf')
        else:
            diff_a = a[0] - a[ia+1]
        if ib + 1 == len_b:
            diff_b = float('inf')
        else:
            diff_b = b[0] - b[ib+1]
        if ic + 1 == len_c:
            diff_c = float('inf')
        else:
            diff_c = c[0] - c[ic+1]

        if diff_a <= diff_b and diff_a <= diff_c:
            ia += 1
        elif diff_b <= diff_a and diff_b <= diff_c:
            ib += 1
        elif diff_c <= diff_a and diff_c <= diff_b:
            ib += 1

    a = a[:ia+1]
    b = b[:ib+1]
    c = c[:ic+1]

    ans = []
    for ai in a:
        for bi in b:
            for ci in c:
                ans.append(ai + bi + ci)
    ans.sort(reverse=True)
    for i in range(k):
        print(ans[i])


Fixed submission:
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)

ab = []
for ai in a:
    for bi in b:
        ab.append(ai + bi)
ab.sort(reverse=True)
if k < len(ab):
    ab = ab[:k]

ans = []
for abi in ab:
    for ci in c:
        ans.append(abi + ci)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())

v = [0] * n
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    v[a] += 1
    v[b] += 1
    g[a].append(b)
    g[b].append(a)

for i in range(n):
    if v[i] % 2 == 1:
        print("No")
        exit()

v4 = 0
for i in range(n):
    if v[i] >= 6:
        print("Yes")
        exit()
    if v[i] == 4:
        v4 += 1

if v4 == 0:
    print("No")
    exit()
if v4 == 1:
    print("No")
    exit()
if v4 >= 3:
    print("Yes")
    exit()


memo = [0] * n
ord = [0] * n
lowlink = [0] * n
articulation = [0] * n

def dfs(v, p, k):
    memo[v] = 1
    ord[v] = k
    lowlink[v] = ord[v]
    isArticulation = False
    count = 0
    for nv in g[v]:
        if memo[nv] == 0:
            count += 1
            dfs(nv, v, k+1)
            lowlink[v] = min(lowlink[v], lowlink[nv])
            if p != -1 and ord[v] <= lowlink[nv]:
                isArticulation = True
        elif nv != p:
            lowlink[v] = min(lowlink[v], ord[nv])

    if p == -1 and count > 1:
        isArticulation = True
    if isArticulation:
        articulation[v] = 1

dfs(0, -1, 0)

count = 0
for i in range(n):
    if v[i] == 4 and articulation[i] == 1:
        count += 1

if count >= 2:
    print("Yes")
else:
    print("No")

Fixed submission:
import sys
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())

v = [0] * n
g = [[] for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    v[a] += 1
    v[b] += 1
    g[a].append(b)
    g[b].append(a)

for i in range(n):
    if v[i] % 2 == 1:
        print("No")
        exit()

v4 = 0
for i in range(n):
    if v[i] >= 6:
        print("Yes")
        exit()
    if v[i] == 4:
        v4 += 1

if v4 == 0:
    print("No")
    exit()
if v4 == 1:
    print("No")
    exit()
if v4 >= 3:
    print("Yes")
    exit()


memo = [0] * n
ord = [0] * n
lowlink = [0] * n
articulation = [0] * n

def dfs(v, p, k):
    memo[v] = 1
    ord[v] = k
    lowlink[v] = ord[v]
    isArticulation = False
    count = 0
    for nv in g[v]:
        if memo[nv] == 0:
            count += 1
            dfs(nv, v, k+1)
            lowlink[v] = min(lowlink[v], lowlink[nv])
            if p != -1 and ord[v] <= lowlink[nv]:
                isArticulation = True
        elif nv != p:
            lowlink[v] = min(lowlink[v], ord[nv])

    if p == -1 and count > 1:
        isArticulation = True
    if isArticulation:
        articulation[v] = 1

dfs(0, -1, 0)

count = 0
for i in range(n):
    if v[i] == 4 and articulation[i] == 1:
        count += 1

if count >= 2:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Time Limit Exceeded):
s = input()
n = len(s)
mod = 998244353

R = [0] * n
B = [0] * n
for i in range(n):
    if s[i] == '0':
        R[i] = 2
    elif s[i] == '1':
        R[i] = 1
        B[i] = 1
    else:
        B[i] = 2

for i in range(n-1):
    R[i+1] += R[i]
    B[i+1] += B[i]


dp = [[0] * (2*n+10) for _ in range(2*n+10)]

if R[0] > 0:
    dp[0][1] = 1
if B[0] > 0:
    dp[0][0] = 1

for i in range(n-1):
    for r in range(2*n+1):
        if R[i+1] >= r+1:
            dp[i+1][r+1] += dp[i][r]
            dp[i+1][r+1] %= mod
        if i+2-r < 0:
            break
        if B[i+1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

for i in range(n-1, 2*n-1):
    for r in range(2*n+1):
        if R[n-1] >= r+1:
            dp[i + 1][r + 1] += dp[i][r]
            dp[i + 1][r + 1] %= mod
        if i+2-r < 0:
            break
        if B[n-1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

ans = 0
for r in range(2*n+1):
    ans += dp[2*n-1][r]
    ans %= mod

print(ans)

Fixed submission:
s = input()
n = len(s)
mod = 998244353

R = [0] * n
B = [0] * n
for i in range(n):
    if s[i] == '0':
        R[i] = 2
    elif s[i] == '1':
        R[i] = 1
        B[i] = 1
    else:
        B[i] = 2

for i in range(n-1):
    R[i+1] += R[i]
    B[i+1] += B[i]


dp = [[0] * (2*n+10) for _ in range(2*n+10)]

if R[0] > 0:
    dp[0][1] = 1
if B[0] > 0:
    dp[0][0] = 1

for i in range(n-1):
    for r in range(2*n+1):
        if R[i+1] >= r+1:
            dp[i+1][r+1] += dp[i][r]
            dp[i+1][r+1] %= mod
        if i+2-r < 0:
            break
        if B[i+1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

for i in range(n-1, 2*n-1):
    for r in range(2*n+1):
        if R[n-1] >= r+1:
            dp[i + 1][r + 1] += dp[i][r]
            dp[i + 1][r + 1] %= mod
        if i+2-r < 0:
            break
        if B[n-1] >= i+2-r:
            dp[i+1][r] += dp[i][r]
            dp[i+1][r] %= mod

ans = 0
for r in range(2*n+1):
    ans += dp[2*n-1][r]
    ans %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
n, w = map(int, input().split())

nap = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*num for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(num):
        if v + nap[i][1] <= num:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(num)):
    if dp[n][v] <= w:
        print(v)
        exit()


Fixed submission:
n, w = map(int, input().split())

nap = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*(10**5+10) for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(10**5+1):
        if v + nap[i][1] <= 10**5+1:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(10**5+1)):
    if dp[n][v] <= w:
        print(v)
        exit()

Buggy python submission (verdict: Runtime Error):
n, w = map(int, input().split())

nap = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*(num) for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(num):
        if v + nap[i][1] <= num:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(num)):
    if dp[n][v] <= w:
        print(v)
        exit()


Fixed submission:
n, w = map(int, input().split())

nap = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')
num = 10**5 + 10
dp = [[INF]*(10**5+10) for _ in range(110)]

dp[0][0] = 0
for i in range(n):
    for v in range(10**5+1):
        if v + nap[i][1] <= 10**5+1:
            dp[i+1][v+nap[i][1]] = min(dp[i+1][v+nap[i][1]], dp[i][v] + nap[i][0])
        dp[i+1][v] = min(dp[i+1][v], dp[i][v])

for v in reversed(range(10**5+1)):
    if dp[n][v] <= w:
        print(v)
        exit()
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

for l in range(1, n+1):
    for i in range(n - l + 1):
        j = i + l
        if (n - l) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])

print(dp[0][n])


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

for l in range(1, n+1):
    for i in range(n - l + 1):
        j = i + l
        if (n - l) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])

print(dp[0][n])

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, m = map(int, input().split())
g = [[] for _ in range(n)]

if n > 2000 or m > 2000:
    exit()

for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = int(input())
if q > 2000:
    exit()

query = [list(map(int, input().split())) for _ in range(q)]

color = [0] * n

def dfs(node, dist, dist_max, col, pre_node):
    if dist > dist_max:
        return
    if color[node] == 0:
        color[node] = col
    if dist == dist_max:
        return
    for next_node in g[node]:
        if next_node == pre_node:
            continue
        dfs(next_node, dist+1, dist_max, col, node)

for v, d, c in query[::-1]:
    v -= 1
    dfs(v, 0, d, c, -1)

for co in color:
    print(co)


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp = [[0] * (n+1) for _ in range(n+1)]

for l in range(1, n+1):
    for i in range(n - l + 1):
        j = i + l
        if (n - l) % 2 == 0:
            dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j-1])
        else:
            dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j-1])

print(dp[0][n])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
a = list(map(int, input().split()))

mod = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]

dp[0][0] = 1
for i in range(1, n+1):
    cum = [0] * (k+2)
    for j in range(k+1):
        cum[j+1] = (cum[j] + dp[i-1][j]) % mod
        dp[i][j] += cum[j+1] - cum[max(0, j-a[i-1])]
        dp[i][j] %= mod

print(dp[n][k])

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))

mod = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]

dp[0][0] = 1
for i in range(1, n+1):
    cum = [0] * (k+2)
    for j in range(k+1):
        cum[j+1] = (cum[j] + dp[i-1][j]) % mod
        dp[i][j] += cum[j+1] - cum[max(0, j-a[i-1])]
        dp[i][j] %= mod

print(dp[n][k])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

INF = float('inf')
dp = [[INF] * (n+1) for _ in range(n+1)]

acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai

for i in range(n+1):
    dp[i][i] = 0
    if i+1 <= n:
        dp[i][i+1] = 0

for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + acum[j] - acum[i])

print(dp[0][n])



Fixed submission:
n = int(input())
a = list(map(int, input().split()))

INF = float('inf')
dp = [[INF] * (n+1) for _ in range(n+1)]

acum = [0] * (n+1)
for i, ai in enumerate(a):
    acum[i+1] += acum[i] + ai

for i in range(n+1):
    dp[i][i] = 0
    if i+1 <= n:
        dp[i][i+1] = 0

for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l
        for k in range(i+1, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + acum[j] - acum[i])

print(dp[0][n])
Buggy python submission (verdict: Runtime Error):
n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

mod = 10**9 + 7

memo = [0] * n
# dp[v][0]:= 頂点vを白に塗ったときの、vを親とする部分木の塗り方の総数
# dp[v][1]:= 頂点vを黒に塗ったときの、vを親とする部分木の塗り方の総数
dp = [[0, 0] for _ in range(n+1)]


def dfs(v):
    if memo[v] != 0:
        return
    memo[v] = 1
    dp[v][0] = 1
    dp[v][1] = 1
    for nv in graph[v]:
        if memo[nv] != 0:
            continue
        dfs(nv)
        dp[v][0] *= (dp[nv][0] + dp[nv][1])
        dp[v][0] %= mod

        dp[v][1] *= dp[nv][0]
        dp[v][1] %= mod

dfs(0)
print((dp[0][0] + dp[0][1]) % mod)


Fixed submission:
import sys
sys.setrecursionlimit(10**7)

n = int(input())
graph = [[] for _ in range(n)]

for _ in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

mod = 10**9 + 7

memo = [0] * n
# dp[v][0]:= 頂点vを白に塗ったときの、vを親とする部分木の塗り方の総数
# dp[v][1]:= 頂点vを黒に塗ったときの、vを親とする部分木の塗り方の総数
dp = [[0, 0] for _ in range(n+1)]


def dfs(v):
    if memo[v] != 0:
        return
    memo[v] = 1
    dp[v][0] = 1
    dp[v][1] = 1
    for nv in graph[v]:
        if memo[nv] != 0:
            continue
        dfs(nv)
        dp[v][0] *= (dp[nv][0] + dp[nv][1])
        dp[v][0] %= mod

        dp[v][1] *= dp[nv][0]
        dp[v][1] %= mod

dfs(0)
print((dp[0][0] + dp[0][1]) % mod)