Buggy python submission (verdict: Time Limit Exceeded):
# https://atcoder.jp/contests/tenka1-2019/submissions/5065329

import sys

input = sys.stdin.readline

N = int(input())
a = [int(input()) for _ in range(N)]
total = sum(a)
MOD = 998244353

'''(1)全体'''
U = pow(3, N, MOD)  # 三角形を構成できない場合を含むRGBの組み合わせ総数

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1
# dp[i][R]:=i番目まででRとなる場合の数

for i in range(N):
    for r in range(total + 1):
        if r - a[i] >= 0:
            dp[i + 1][r] += dp[i][r - a[i]]
        dp[i + 1][r] += 2 * dp[i][r]
        # g, bに加算する分で、2回起こる
# print(dp)

single_circle = 0
for r in range(total + 1):
    if r >= (total / 2):
        single_circle += dp[N][r]
# print(single_circle)

'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    # dp[i][R]:=i番目まででRとなる場合の数

    for i in range(N):
        for r in range(int(total / 2) + 1):
            if r - a[i] >= 0:
                dp2[i + 1][r] += dp2[i][r - a[i]]
            dp2[i + 1][r] += dp2[i][r]
    # print(dp2)

two_circle_intersect = dp2[N][int(total / 2)] if total % 2 == 0 else 0

'''(3)３円の積集合'''
three_circle_intersect = 0

'''(4)解答'''
ans = 0

ans += U
ans %= MOD

ans -= 3 * single_circle
ans %= MOD

ans += 3 * two_circle_intersect
ans %= MOD

ans -= three_circle_intersect
ans %= MOD

print(ans)

Fixed submission:
# https://atcoder.jp/contests/tenka1-2019/submissions/5065329

import sys

input = sys.stdin.readline

N = int(input())
a = [int(input()) for _ in range(N)]
total = sum(a)
MOD = 998244353

'''(1)全体'''
U = pow(3, N, MOD)  # 三角形を構成できない場合を含むRGBの組み合わせ総数

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1
# dp[i][R]:=i番目まででRとなる場合の数

for i in range(N):
    for r in range(total + 1):
        if r - a[i] >= 0:
            dp[i + 1][r] += dp[i][r - a[i]]
        dp[i + 1][r] += 2 * dp[i][r]
        dp[i + 1][r] %= MOD
        # g, bに加算する分で、2回起こる
# print(dp)

single_circle = 0
for r in range(total + 1):
    if r >= (total / 2):
        single_circle += dp[N][r]
# print(single_circle)

'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    # dp[i][R]:=i番目まででRとなる場合の数

    for i in range(N):
        for r in range(int(total / 2) + 1):
            if r - a[i] >= 0:
                dp2[i + 1][r] += dp2[i][r - a[i]]
            dp2[i + 1][r] += dp2[i][r]
            dp2[i + 1][r] %= MOD
    # print(dp2)

two_circle_intersect = dp2[N][int(total / 2)] if total % 2 == 0 else 0

'''(3)３円の積集合'''
three_circle_intersect = 0

'''(4)解答'''
ans = 0

ans += U
ans %= MOD

ans -= 3 * single_circle
ans %= MOD

ans += 3 * two_circle_intersect
ans %= MOD

ans -= three_circle_intersect
ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353

N = int(input())
a = [int(input()) for _ in range(N)]

total = sum(a)
sup = (total - 1) // 2

# total > 2 * max(R,G,B)
# を満たすR,G,Bの場合の数
# (total - 1) // 2 >= max(R,G,B)

dp = [[[0 for _ in range(total + 1)] for _ in range(total + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
# dp[i][R][G]:=i番目まででRGとなる総数

# 枝刈り
# sup = (total - 1) // 2
# sup >= max(R,G,B)
# supを超えるRGBはdp遷移時にカット

for i in range(N):
    # a[i]はRGBのいずれかに加算
    for s in range(2 * sup + 1):
        for r in range(a[i], min(s, sup) + 1):
            g = s - r
            dp[i + 1][r][g] += dp[i][r - a[i]][g]
            dp[i + 1][r][g] %= MOD
        for g in range(a[i], min(s, sup) + 1):
            r = s - g
            dp[i + 1][r][g] += dp[i][r][g - a[i]]
            dp[i + 1][r][g] %= MOD
        for r in range(min(s, sup) + 1):
            g = s - r
            dp[i + 1][r][g] += dp[i][r][g]
            dp[i + 1][r][g] %= MOD
            # Bに対応

ans = sum(dp[N][r][g] for r in range(sup + 1) for g in range(sup + 1) if total - r - g <= sup)
ans %= MOD
print(ans)


Fixed submission:
# https://atcoder.jp/contests/tenka1-2019/submissions/5065329

import sys

input = sys.stdin.readline

N = int(input())
a = [int(input()) for _ in range(N)]
total = sum(a)
MOD = 998244353

'''(1)全体'''
U = pow(3, N, MOD)  # 三角形を構成できない場合を含むRGBの組み合わせ総数

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1
# dp[i][R]:=i番目まででRとなる場合の数

for i in range(N):
    for r in range(total + 1):
        if r - a[i] >= 0:
            dp[i + 1][r] += dp[i][r - a[i]]
        dp[i + 1][r] += 2 * dp[i][r]
        dp[i + 1][r] %= MOD
        # g, bに加算する分で、2回起こる
# print(dp)

single_circle = 0
for r in range(total + 1):
    if r >= (total / 2):
        single_circle += dp[N][r]
# print(single_circle)

'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    # dp[i][R]:=i番目まででRとなる場合の数

    for i in range(N):
        for r in range(int(total / 2) + 1):
            if r - a[i] >= 0:
                dp2[i + 1][r] += dp2[i][r - a[i]]
            dp2[i + 1][r] += dp2[i][r]
            dp2[i + 1][r] %= MOD
    # print(dp2)

two_circle_intersect = dp2[N][int(total / 2)] if total % 2 == 0 else 0

'''(3)３円の積集合'''
three_circle_intersect = 0

'''(4)解答'''
ans = 0

ans += U
ans %= MOD

ans -= 3 * single_circle
ans %= MOD

ans += 3 * two_circle_intersect
ans %= MOD

ans -= three_circle_intersect
ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
MOD = 998244353

N = int(input())
a = [int(input()) for _ in range(N)]

total = sum(a)
sup = (total - 1) // 2

# total > 2 * max(R,G,B)
# を満たすR,G,Bの場合の数
# (total - 1) // 2 >= max(R,G,B)

dp = [[[0 for _ in range(total + 1)] for _ in range(total + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
# dp[i][R][G]:=i番目まででRGとなる総数

# 枝刈り
# sup = (total - 1) // 2
# sup >= max(R,G,B)
# supを超えるRGBはdp遷移時にカット

for i in range(N):
    # a[i]はRGBのいずれかに加算
    for s in range(2 * sup + 1):
        for r in range(min(s, sup) + 1):
            g = s - r
            if r - a[i] >= 0:
                dp[i + 1][r][g] += dp[i][r - a[i]][g]
                dp[i + 1][r][g] %= MOD
            if g - a[i] >= 0:
                dp[i + 1][r][g] += dp[i][r][g - a[i]]
                dp[i + 1][r][g] %= MOD
            dp[i + 1][r][g] += dp[i][r][g]
            dp[i + 1][r][g] %= MOD
            # Bに対応

ans = 0
for r in range(sup + 1):
    for g in range(sup + 1):
        if total - r - g > sup: continue
        ans += dp[N][r][g]
        ans %= MOD
print(ans)


Fixed submission:
# https://atcoder.jp/contests/tenka1-2019/submissions/5065329

import sys

input = sys.stdin.readline

N = int(input())
a = [int(input()) for _ in range(N)]
total = sum(a)
MOD = 998244353

'''(1)全体'''
U = pow(3, N, MOD)  # 三角形を構成できない場合を含むRGBの組み合わせ総数

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1
# dp[i][R]:=i番目まででRとなる場合の数

for i in range(N):
    for r in range(total + 1):
        if r - a[i] >= 0:
            dp[i + 1][r] += dp[i][r - a[i]]
        dp[i + 1][r] += 2 * dp[i][r]
        dp[i + 1][r] %= MOD
        # g, bに加算する分で、2回起こる
# print(dp)

single_circle = 0
for r in range(total + 1):
    if r >= (total / 2):
        single_circle += dp[N][r]
# print(single_circle)

'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    # dp[i][R]:=i番目まででRとなる場合の数

    for i in range(N):
        for r in range(int(total / 2) + 1):
            if r - a[i] >= 0:
                dp2[i + 1][r] += dp2[i][r - a[i]]
            dp2[i + 1][r] += dp2[i][r]
            dp2[i + 1][r] %= MOD
    # print(dp2)

two_circle_intersect = dp2[N][int(total / 2)] if total % 2 == 0 else 0

'''(3)３円の積集合'''
three_circle_intersect = 0

'''(4)解答'''
ans = 0

ans += U
ans %= MOD

ans -= 3 * single_circle
ans %= MOD

ans += 3 * two_circle_intersect
ans %= MOD

ans -= three_circle_intersect
ans %= MOD

print(ans)