Buggy python submission (verdict: Runtime Error):

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import numpy as np




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_num = sum(data)
    mod = 998244353

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    dp2 = np.zeros(sum_num + 1, dtype=np.int64)
    dp2[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp2
        dp2[now_num:] += prev[:-now_num]
        dp2 %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    for i in range(math.ceil(sum_num / 2), sum_num + 1):
        hikukazu += dp[i]
    if sum_num % 2 == 0:
        hikukazu -= dp2[sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)
    # print(dp)


if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    mod = 998244353

    dp = [defaultdict(int) for i in range(num)]
    for i in range(num):
        now_num = data[i]
        if i == 0:
            dp[i][0] = 2
            dp[i][now_num] = 1
            continue
        for key, value in dp[i - 1].items():
            dp[i][key] += value * 2
            dp[i][key + now_num] += value
            dp[i][key] %= mod
            dp[i][key + now_num] %= mod

    dp2 = [defaultdict(int) for i in range(num)]
    for i in range(num):
        now_num = data[i]
        if i == 0:
            dp2[i][0] = 1
            dp2[i][now_num] = 1
            continue
        for key, value in dp2[i - 1].items():
            dp2[i][key] += value
            dp2[i][key + now_num] += value
            dp2[i][key] %= mod
            dp2[i][key + now_num] %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    sum_num = sum(data)
    for key, value in dp[num - 1].items():
        if key >= math.ceil(sum_num / 2):
            hikukazu += value
    if sum_num % 2 == 0:
        hikukazu -= dp2[num - 1][sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)
    # print(dp)


if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools




def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    mod = 998244353

    dp = [defaultdict(int) for i in range(num)]
    dp2 = [defaultdict(int) for i in range(num)]
    for i in range(num):
        now_num = data[i]
        if i == 0:
            dp[i][0] = 2
            dp[i][now_num] = 1
            dp2[i][0] = 1
            dp2[i][now_num] = 1
            continue
        for key in dp[i - 1].keys():
            dp[i][key] += dp[i - 1][key] * 2
            dp[i][key + now_num] += dp[i - 1][key]
            dp[i][key] %= mod
            dp[i][key + now_num] %= mod
            dp2[i][key] += dp2[i - 1][key]
            dp2[i][key + now_num] += dp2[i - 1][key]
            dp2[i][key] %= mod
            dp2[i][key + now_num] %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    sum_num = sum(data)
    for key in dp[num - 1].keys():
        if key >= math.ceil(sum_num / 2):
            hikukazu += dp[num - 1][key]
    if sum_num % 2 == 0:
        hikukazu -= dp2[num - 1][sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()



Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

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

def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_data = sum(data)

    dp = [defaultdict(int) for i in range(num)]

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2


    dp[0][0] = 2
    dp[0][data[0]] = 1

    dp2 = [defaultdict(int) for i in range(num)]
    dp2[0][0] = 1
    dp2[0][data[0]] = 1

    for i in range(1, num):
        now_num = data[i]
        for dic_num in dp[i-1].keys():
            dp[i][dic_num] += dp[i - 1][dic_num] * 2
            dp[i][dic_num+now_num] += dp[i - 1][dic_num]
            dp2[i][dic_num] += dp2[i - 1][dic_num]
            dp2[i][dic_num + now_num] += dp2[i - 1][dic_num]

    count = 0
    for i in dp[num-1].keys():
        if i >= max_length:
            count += dp[num - 1][i]


    count2 = 0
    for i in dp2[num - 1].keys():
        if i >= max_length:
            count2 += dp2[num - 1][i]

    zennbu = 3 ** num - 3*(2**num - 2) - 3
    hiku = 3 * (count - 2 * count2 + 1)
    ans = zennbu - hiku
    print(ans % 998244353)

    # print('-----')
    # print(sum_data)
    # print(max_length)
    # print(count, count2)
    # print(dp)
    # print(dp2)



if __name__ == '__main__':
    main()
    # print(300**300)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

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

def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_data = sum(data)

    dp = [defaultdict(int) for i in range(num)]

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2


    dp[0][0] = 2
    dp[0][data[0]] = 1

    for i in range(1, num):
        now_num = data[i]
        for dic_num in dp[i-1].keys():
            dp[i][dic_num] += dp[i - 1][dic_num] * 2
            dp[i][dic_num+now_num] += dp[i - 1][dic_num]

    count = 0
    for i in dp[num-1].keys():
        if i >= max_length:
            count += dp[num - 1][i]



    dp2 = [defaultdict(int) for i in range(num)]
    dp2[0][0] = 1
    dp2[0][data[0]] = 1

    for i in range(1, num):
        now_num = data[i]
        for dic_num in dp2[i - 1].keys():
            dp2[i][dic_num] += dp2[i - 1][dic_num]
            dp2[i][dic_num + now_num] += dp2[i - 1][dic_num]

    count2 = 0
    for i in dp2[num - 1].keys():
        if i >= max_length:
            count2 += dp2[num - 1][i]

    zennbu = 3 ** num - 3*(2**num - 2) - 3
    hiku = 3 * (count - 2 * count2 + 1)
    ans = zennbu - hiku
    print(ans % 998244353)

    # print('-----')
    # print(sum_data)
    # print(max_length)
    # print(count, count2)
    # print(dp)
    # print(dp2)



if __name__ == '__main__':
    main()
    # print(300**300)


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):

def kari():
    N = list(map(int, input().split()))
    A, B = map(int, input().split())

ans_num = 0

# def check(a_sum, b_sum, data, max_length):
#     global ans_num
#     c_sum = sum(data)
#     if c_sum >= max_length:
#         return
#     ans_num += 1


def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_data = sum(data)

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2

    # print(sum_data, max_length)

    # check([data[0]], [], [], 1, data[1:], max_length, num, data[0], 0, 0)
    # check([], [data[0]], [], 1, data[1:], max_length, num, 0, data[0], 0)
    # check([], [], [data[0]], 1, data[1:], max_length, num, 0, 0, data[0])

    check(1, data, max_length, num, data[0], 0, 0)
    # check(1, data, max_length, num, 0, data[0], 0)
    # check(1, data, max_length, num, 0, 0, data[0])

    global ans_num
    print((ans_num * 3) % 998244353)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):

def kari():
    N = list(map(int, input().split()))
    A, B = map(int, input().split())

ans_num = 0

# def check(a_sum, b_sum, data, max_length):
#     global ans_num
#     c_sum = sum(data)
#     if c_sum >= max_length:
#         return
#     ans_num += 1


def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



def main():
    num = int(input())
    data = [int(input()) for i in range(num)]
    sum_data = sum(data)

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2

    # print(sum_data, max_length)

    # check([data[0]], [], [], 1, data[1:], max_length, num, data[0], 0, 0)
    # check([], [data[0]], [], 1, data[1:], max_length, num, 0, data[0], 0)
    # check([], [], [data[0]], 1, data[1:], max_length, num, 0, 0, data[0])

    check(1, data, max_length, num, data[0], 0, 0)
    check(1, data, max_length, num, 0, data[0], 0)
    check(1, data, max_length, num, 0, 0, data[0])

    global ans_num
    print(ans_num % 998244353)


if __name__ == '__main__':
    main()


Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
MOD = 998244353

N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2 # 赤以外を採用
    dp[a:] += prev[:-a] # 赤
    dp %= MOD

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)