Problem p03009 (python)

Fixed submission:
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


fact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = fact[i] * (i + 1)
    fact[i + 1] %= MOD

# fact_sum = fact[1] + fact[2] + ... + fact[n]
fact_sum = 0
for i in range(1, n + 1):
    fact_sum += fact[i]
    fact_sum %= MOD

dp = [0] * (h + 1)
ru = [0] * (h + 2)
dp[0] = 1
ru[1] = 1
for i in range(h):
    l = max(i + 1 - d, 0)
    dp[i + 1] += (ru[i + 1] - ru[l]) * fact_sum
    dp[i + 1] %= MOD
    ru[i + 2] = ru[i + 1] + dp[i + 1]
    ru[i + 2] %= MOD

print((dp[-1] * fact[n] * pow(fact_sum, MOD - 2, MOD)) % MOD)

Buggy submission (verdict: Runtime Error):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


if d != 1:
    print(re)

fact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = fact[i] * (i + 1)
    fact[i + 1] %= MOD

# fact_sum = fact[1] + fact[2] + ... + fact[n]
fact_sum = 0
for i in range(1, n + 1):
    fact_sum += fact[i]
    fact_sum %= MOD

dp = [0] * (h + 1)
dp[0] = 1
for i in range(h):
    dp[i + 1] = dp[i] * fact_sum
    dp[i + 1] %= MOD

print((dp[-1] - dp[-2] * (fact_sum - fact[-1])) % MOD)

Buggy submission (verdict: Runtime Error):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


if n * h + h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HN)
ru = [[0] * (n + 2) for i in range(h + 1)]
ru[0][n + 1] = 1
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        dp[i + 1][1] += ru[i + 1 - diff][n + 1]
        dp[i + 1][1] %= MOD

    # j - 1 -> j にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * j
        dp[i + 1][j] %= MOD

    for j in range(n + 1):
        ru[i + 1][j + 1] = ru[i + 1][j] + dp[i + 1][j]
        ru[i + 1][j + 1] %= MOD

print(dp[-1][-1] % MOD)

Buggy submission (verdict: Runtime Error):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


if n * h >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HN)
ru = [[0] * (n + 2) for i in range(h + 1)]
ru[0][n + 1] = 1
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        dp[i + 1][1] += ru[i + 1 - diff][n + 1]

    # j - 1 -> j にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * j
        dp[i + 1][j] %= MOD

    for j in range(n + 1):
        ru[i + 1][j + 1] = ru[i + 1][j] + dp[i + 1][j]
        ru[i + 1][j + 1] %= MOD

print(dp[-1][-1] % MOD)

Buggy submission (verdict: Runtime Error):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


if n * h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt]
            dp[i + 1][1] %= MOD

    # j - 1 -> j にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * j
        dp[i + 1][j] %= MOD

print(dp[-1][-1] % MOD)

Buggy submission (verdict: Runtime Error):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


if n * h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
            dp[i + 1][1] %= MOD

    # j -> j + 1 にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
        dp[i + 1][j] %= MOD

print(dp[-1][-1] % MOD)

Buggy submission (verdict: Runtime Error):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


if n * h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
            dp[i + 1][1] %= MOD

    # j -> j + 1 にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
        dp[i + 1][j] %= MOD

print(dp[-1][-1])

Buggy submission (verdict: Runtime Error):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
            dp[i + 1][1] %= MOD

    # j -> j + 1 にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
        dp[i + 1][j] %= MOD

print(dp[-1][-1])

Buggy submission (verdict: Runtime Error):
n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

w_ab = []
v_ab = []

if ga < gb:
    w_ab.append(ga)
    v_ab.append(gb)
if sa < sb:
    w_ab.append(sa)
    v_ab.append(sb)
if ba < bb:
    w_ab.append(ba)
    v_ab.append(bb)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])
ans = 0
length = len(w_ab)
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
n = ans

w_ab = []
v_ab = []

if ga > gb:
    w_ab.append(gb)
    v_ab.append(ga)
if sa > sb:
    w_ab.append(sb)
    v_ab.append(sa)
if ba > bb:
    w_ab.append(bb)
    v_ab.append(ba)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])

length = len(w_ab)
ans = 0
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
print(ans)