Problem p03070 (python)

Fixed submission:
import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

Buggy submission (verdict: Runtime Error):
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3

memo = np.full(((n+1), (n * max(aa) + 1), 2), -1, dtype=np.int64)
def dfs12(i, c):
    if 0 <= memo[i, c, 0]:
        return memo[i, c]

    if i == n:
        memo[i, c, 0] = 3 if total <= (2 * c) else 0
        memo[i, c, 1] = 3 if total == (2 * c) else 0
        return memo[i, c]

    v0 = dfs12(i + 1, c)
    v1 = dfs12(i + 1, c + aa[i])

    memo[i, c, 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[i, c, 1] = (v0[1] + v1[1]) % 998244353
    return memo[i, c]

a, b = dfs12(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

Buggy submission (verdict: Runtime Error):
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo1[i][c] = acc
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Buggy submission (verdict: Runtime Error):
import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = max(0, memo0[i][c])
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = max(0, memo1[i][c])
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Buggy submission (verdict: Runtime Error):
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = max(0, memo0[i][c])
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = max(0, memo1[i][c])
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Buggy submission (verdict: Runtime Error):
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = max(0, memo0[i][c])
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = max(0, memo1[i][c])
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Buggy submission (verdict: Runtime Error):
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        ret = 1 if c < a + b else 0
        memo[(a, b, c)] = ret
        return ret
    if total < (2 * c)
        memo[(a, b, c)] = 0
        return 0
    if (a, b, c) in memo:
        return memo[(a, b, c)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(v0[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

    memo[(a, b, c)] = ret
    return ret

print(dfs(0, 0, 0, 0))

Buggy submission (verdict: Runtime Error):
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

n = readInt()
aa = []
for i in range(n):
    aa.append(readInt())

#memo = {}


def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
#    if (a, b, c, i) in memo:
#        return memo[(a, b, c, i)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(*v0, i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(*v1, i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(*v2, i + 1)) % 998244353

#    memo[(a, b, c, i)] = ret
    return ret


ret = dfs(0, 0, 0, 0)
print(ret)

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

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

n = readInt()
aa = []
for i in range(n):
    aa.append(readInt())

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
    if (a,b,c,i) in memo:
        return memo[(a,b,c,i)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(*v0, i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(*v1, i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(*v2, i + 1)) % 998244353


    memo[(a,b,c,i)] = ret
    return ret

ret = dfs(0, 0, 0, 0)
print(ret)

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

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(' ')]

n = readInt()
aa = [readInt() for _ in range(n)]

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
    if (a,b,c,i) in memo:
        return memo[(a,b,c,i)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(*v0, i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(*v1, i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(*v2, i + 1)) % 998244353


    memo[(a,b,c,i)] = ret
    return ret

ret = dfs(0, 0, 0, 0)
print(ret)