Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  # type: int


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, a: "List[int]"):

    S = sum(a)
    dp = [defaultdict(int) for _ in range(N)]
    dp2 = [defaultdict(int) for _ in range(N)]
    dp[0][0] = 2
    dp[0][a[0]] = 1
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        for key in dp[i-1]:
            dp[i][key] += 2*dp[i-1][key]
            dp[i][key] %= MOD
            dp[i][key+a[i]] += dp[i-1][key]
            dp[i][key+a[i]] %= MOD

        for key in dp2[i-1]:
            dp2[i][key] += dp2[i-1][key]
            dp2[i][key] %= MOD
            dp2[i][key+a[i]] += dp2[i-1][key]
            dp2[i][key+a[i]] %= MOD

    ans = power(3, N) - sum([dp[N-1][i] for i in range(-(-S//2), S+1)])*3
    ans %= MOD
    if S % 2 == 0:              #
        ans += 3*dp2[N-1][-(-S//2)]
        ans %= MOD
    print(ans)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  # type: int


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, a: "List[int]"):

    S = sum(a)
    # dp = [defaultdict(int) for _ in range(N)]
    dp = [[0]*(S+1) for _ in range(N)]
    # dp2 = [defaultdict(int) for _ in range(N)]
    dp2 = [[0]*(S+1) for _ in range(N)]
    dp[0][0] = 2
    dp[0][a[0]] = 1
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        # for key in dp[i-1]:
        for key in range(S+1):
            dp[i][key] = 2*dp[i-1][key]+dp[i-1][key-a[i]]
            dp[i][key] %= MOD
            dp2[i][key] = dp2[i-1][key] + dp2[i-1][key-a[i]]
            dp2[i][key] %= MOD

    # ans = power(3, N) - sum([dp[N-1][i] for i in range(-(-S//2), S+1)])*3
    ans = power(3, N) - sum(dp[N-1][-(-S//2):])*3
    ans %= MOD
    if S % 2 == 0:              #
        ans += 3*dp2[N-1][-(-S//2)]
        ans %= MOD
    print(ans)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  # type: int


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, a: "List[int]"):

    S = sum(a)
    dp = [defaultdict(int) for _ in range(N)]
    dp2 = [defaultdict(int) for _ in range(N)]
    dp[0][0] = 2
    dp[0][a[0]] = 1
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        for key in dp[i-1]:
            dp[i][key] += 2*dp[i-1][key]
            dp[i][key] %= MOD
            dp[i][key+a[i]] += dp[i-1][key]
            dp[i][key+a[i]] %= MOD

        for key in dp2[i-1]:
            dp2[i][key] += dp2[i-1][key]
            dp2[i][key] %= MOD
            dp2[i][key+a[i]] += dp2[i-1][key]
            dp2[i][key+a[i]] %= MOD

    ans = power(3, N) - sum([dp[N-1][i] for i in range(-(-S//2), S+1)])*3
    ans %= MOD
    if S % 2 == 0:              #
        ans += 3*dp2[N-1][-(-S//2)]
        ans %= MOD
    print(ans)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  # type: int


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, a: "List[int]"):

    S = sum(a)
    # dp = [defaultdict(int) for _ in range(N)]
    dp = [[0]*(S+1) for _ in range(N)]
    # dp2 = [defaultdict(int) for _ in range(N)]
    dp2 = [[0]*(S+1) for _ in range(N)]
    dp[0][0] = 2
    dp[0][a[0]] = 1
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        # for key in dp[i-1]:
        for key in range(S+1):
            dp[i][key] = 2*dp[i-1][key]+dp[i-1][key-a[i]]
            dp[i][key] %= MOD
            dp2[i][key] = dp2[i-1][key] + dp2[i-1][key-a[i]]
            dp2[i][key] %= MOD

    # ans = power(3, N) - sum([dp[N-1][i] for i in range(-(-S//2), S+1)])*3
    ans = power(3, N) - sum(dp[N-1][-(-S//2):])*3
    ans %= MOD
    if S % 2 == 0:              #
        ans += 3*dp2[N-1][-(-S//2)]
        ans %= MOD
    print(ans)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  # type: int


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, a: "List[int]"):

    # R >= -(-S//2)をDPで数える
    S = sum(a)
    # i番目(0-indexed)までを見て、Rとなる場合の数dp[i][R]
    # 0<=R<=Sなので、S+1までとっておく
    dp = [[0]*(S+1) for _ in range(N)]
    # dp[i][R]は、a[i]が青の場合がdp[i-1][R]通り
    #             a[i]が緑の場合がdp[i-1][R]通り
    #             a[i]が赤い場合がdp[i-1][R-a[i]]通り
    dp[0][0] += 2
    dp[0][a[0]] += 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        for r in range(S+1):
            dp[i][r] = 2*dp[i-1][r]
            dp[i][r] += dp[i-1][r-a[i]]  # r-a[i]が負となる場合は初期値0になっているはずなので問題なし
            dp[i][r] %= MOD
    # print(*dp, sep="\n")
    # print("---")

    # R == S//2 かつ B == 0 の場合を数える
    dp2 = [[0]*(S+1) for _ in range(N)]
    # dp2[i][R]は、a[i]が緑の場合がdp2[i-1][R]通り
    #              a[i]が赤い場合がdp2[i-1][R-a[i]]通り
    #              a[i]は青くならない
    dp2[0][0] += 1
    dp2[0][a[0]] += 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        for r in range(S+1):
            dp2[i][r] = dp2[i-1][r]
            dp2[i][r] += dp2[i-1][r-a[i]]
            dp2[i][r] %= MOD
    # print(*dp2, sep="\n")

    # 最終的に求めたいのは、3**N - 3*{R>=-(-S//2)} + 3*{R==S//2andB==0}
    ans = power(3, N)
    a1 = sum(dp[N-1][-(-S//2):]) % MOD
    a2 = dp2[N-1][-(-S//2)] % MOD
    ans -= 3*a1
    ans %= MOD
    if S % 2 == 0:              #
        ans += 3*a2
        ans %= MOD
    print(ans)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()


Fixed submission:
#!/usr/bin/env python3
import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  # type: int


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def solve(N: int, a: "List[int]"):

    S = sum(a)
    # dp = [defaultdict(int) for _ in range(N)]
    dp = [[0]*(S+1) for _ in range(N)]
    # dp2 = [defaultdict(int) for _ in range(N)]
    dp2 = [[0]*(S+1) for _ in range(N)]
    dp[0][0] = 2
    dp[0][a[0]] = 1
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(1, N):     # i+1番目の数字まで使ったとき
        # for key in dp[i-1]:
        for key in range(S+1):
            dp[i][key] = 2*dp[i-1][key]+dp[i-1][key-a[i]]
            dp[i][key] %= MOD
            dp2[i][key] = dp2[i-1][key] + dp2[i-1][key-a[i]]
            dp2[i][key] %= MOD

    # ans = power(3, N) - sum([dp[N-1][i] for i in range(-(-S//2), S+1)])*3
    ans = power(3, N) - sum(dp[N-1][-(-S//2):])*3
    ans %= MOD
    if S % 2 == 0:              #
        ans += 3*dp2[N-1][-(-S//2)]
        ans %= MOD
    print(ans)

    return


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
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, a)


if __name__ == '__main__':
    main()