Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= -(-total//2):
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp2[0][0] = 1
    for i in range(N):
        for j in dp1[i]:
            nj = min(j+A[i], half+1)
            dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j] * 2) % MOD
            dp1[i+1][nj] = (dp1[i+1][nj] + dp1[i][j]) % MOD
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % MOD
            dp2[i+1][nj] = (dp2[i+1][nj] + dp2[i][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N]:
        if t >= -(-total//2):
            ans = (ans - dp1[N][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    dp1 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp2[0][0] = 1
    for i in range(N):
        for j in dp1[i]:
            dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j] * 2) % MOD
            dp1[i+1][j+A[i]] = (dp1[i+1][j+A[i]] + dp1[i][j]) % MOD
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % MOD
            dp2[i+1][j+A[i]] = (dp2[i+1][j+A[i]] + dp2[i][j]) % MOD

    ans = (3**N) % MOD
    for t in dp1[N]:
        if t >= -(-total//2):
            ans = (ans - dp1[N][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()


Fixed submission:
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    A.sort(reverse=True)
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= half:
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == half:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()