Problem:
 Score : 600 points    Problem Statement You are given N integers. The i -th integer is a_i .
Find the number, modulo 998244353 , of ways to paint each of the integers red, green or blue so that the following condition is satisfied:   Let R , G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R , G and B .       Constraints  3 \leq N \leq 300  1 \leq a_i \leq 300(1\leq i\leq N)  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  a_1  :  a_N       Output Print the number, modulo 998244353 , of ways to paint each of the integers red, green or blue so that the condition is satisfied.        Sample Input 1 4
1
1
1
2      Sample Output 1 18  We can only paint the integers so that the lengths of the sides of the triangle will be 1 , 2 and 2 , and there are 18 such ways.       Sample Input 2 6
1
3
2
3
5
2      Sample Output 2 150       Sample Input 3 20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4      Sample Output 3 563038556

Solution (Python):
import numpy as np
N = int(input())
a = [int(input()) for _ in range(N)]
mod = 998244353
suma = sum(a)
memo = np.zeros((N+1, suma+1), dtype=np.int)
memo[0][0] = 1
memoe = np.zeros((N+1, suma+1), dtype=np.int)
memoe[0][0] = 1

ttl = 3
for i in range(N-1):
  ttl *=3
  ttl %= mod

for i in range(1, N+1):
  memotmp = memo[i-1]
  memotmpe = memoe[i-1]
  memotmp = np.concatenate((np.zeros((a[i-1]), dtype=np.int), memotmp),axis=1)
  memotmpe = np.concatenate((np.zeros((a[i-1]), dtype=np.int), memotmpe),axis=1)
  memo[i] = (memo[i-1]*2 + memotmp[:suma+1])%mod
  memoe[i] = (memoe[i-1] + memotmpe[:suma+1])%mod

ans = sum(memo[N][(suma-1)//2+1:])
if suma%2==0:
  ans -= memoe[N][suma/2]
  
print(((ttl - ans*3)%mod+mod)%mod)

Solution (Python):
def d_three_colors(N, A, MOD=998244353):
    
    a_sum = sum(A)

    
    
    
    dp0 = [0] * (a_sum + 1)
    dp0[0] = 1
    for a in A:
        for s in range(a_sum, a - 1, -1):
            
            
            dp0[s] = (dp0[s] + 2 * dp0[s - a]) % MOD

    
    dp1 = [0] * (a_sum + 1)
    dp1[0] = 1
    for a in A:
        for s in range(a_sum, a - 1, -1):
            
            
            dp1[s] = (dp1[s] + dp1[s - a]) % MOD

    ans = pow(3, N, MOD)  
    for l in range(a_sum // 2 + 1):
        
        ans = (ans - 3 * dp0[l]) % MOD
    if a_sum % 2 == 0:
        
        ans = (ans + 3 * dp1[a_sum // 2]) % MOD
    return ans

N = int(input())
A = [int(input()) for _ in range(N)]
print(d_three_colors(N, A))

Solution (Python):
def main():
	N = int(input())
	A = [0]*N
	MOD = 998244353
	summation = 0

	for i in range(N):
		A[i] = int(input())
		summation += A[i]

	
	dp = [[0 for _ in range(summation+1)] for _ in range(N)]
	dp[0][0] = 2 
	dp[0][A[0]] = 1 

	for i in range(1, N):
		for j in range(len(dp[i])):
			dp[i][j] += dp[i-1][j] * 2 % MOD 
			dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j - A[i] <= len(dp[i]) else 0 

	
	ans = (3 ** N) % MOD
	ceil = summation // 2
	if summation % 2 != 0:
		ceil += 1
	ans -= sum([dp[N-1][r] for r in range(ceil, summation+1)])*3
	ans %= MOD

	if summation %2 == 0:
		
		dp  =[[0 for _ in range(summation//2+1)] for _ in range(N)]
		dp[0][0] = 1 
		dp[0][A[0]] = 1
		for i in range(1, N):
			for j in range(len(dp[i])):
				dp[i][j] += dp[i-1][j] % MOD
				dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j-A[i] <= len(dp[i]) else 0
		ans += dp[N-1][summation//2]*3
		ans %= MOD

	print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
m = 998244353
S = a.sum()


DP_A = np.zeros((N+1, S+1), dtype=np.int64)

DP_B = np.zeros((N+1, S+1), dtype=np.int64)

DP_A[0, 0] = 1
DP_B[0, 0] = 1














for t in range(N):
    DP_A[t+1, :] = (DP_A[t, :]) * 2 % m
    DP_A[t+1, a[t]:] += DP_A[t, :-a[t]] % m
    DP_B[t+1, :] = (DP_B[t, :]) % m
    DP_B[t+1, a[t]:] += DP_B[t, :-a[t]] % m

res1 = DP_A[N, int(np.ceil(S/2)):].sum()
res2 = DP_B[N, int(np.ceil(S/2))] if S % 2 == 0 else 0
res = (3 ** N - res1 * 3 + res2 * 3) % m
print(res)

Solution (Python):
def main():
	N = int(input())
	A = [0]*N
	MOD = 998244353
	summation = 0

	for i in range(N):
		A[i] = int(input())
		summation += A[i]

	
	dp = [[0 for _ in range(summation+1)] for _ in range(N)]
	dp[0][0] = 2 
	dp[0][A[0]] = 1 

	for i in range(1, N):
		for j in range(len(dp[i])):
			dp[i][j] += dp[i-1][j] * 2 % MOD 
			dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j - A[i] <= len(dp[i]) else 0 

	
	ans = (3 ** N) % MOD
	ceil = summation // 2
	if summation % 2 != 0:
		ceil += 1
	ans -= sum([dp[N-1][r] for r in range(ceil, summation+1)])*3
	ans %= MOD

	if summation %2 == 0:
		
		dp  =[[0 for _ in range(summation//2+1)] for _ in range(N)]
		dp[0][0] = 1 
		dp[0][A[0]] = 1
		for i in range(1, N):
			for j in range(len(dp[i])):
				dp[i][j] += dp[i-1][j] % MOD
				dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j-A[i] <= len(dp[i]) else 0
		ans += dp[N-1][summation//2]*3
		ans %= MOD

	print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
alist = [int(input()) for i in range(N)]
import numpy as np

alist.sort(reverse=False) 
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2


dptableA = np.zeros((N+1, S+1), dtype=np.int) 
dptableA[N, int(np.ceil(Sharf)):] = 1

dptableB = np.zeros((N+1, S+1), dtype=np.int) 
if S %2 == 0:
    dptableB[N, int(Sharf)] = 1 


for i in range(N, 0, -1): 
    n = i - 1
    an = alist[n]
    asn = asum[n]
    dptableA[n, 0:asn+1] = (2*dptableA[n+1, 0:asn+1] + dptableA[n+1, an:an+asn+1])%MOD
    
    dptableB[n, 0:asn+1] = (dptableB[n+1, 0:asn+1] + dptableB[n+1, an:an+asn+1])%MOD
    
retA, retB = dptableA[0,0], dptableB[0,0]

ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)

Solution (Python):
def dp_table(*counts):  
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for _ in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = [[0] * (sum_A+1) for i in range(N)]
    

    
    dp[0][A[0]] = 1
    dp[0][0] = 2  

    
    dp2 = [[0] * (sum_A+1) for i in range(N)]  
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  

    
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + \
                    (dp[i - 1][length] << 1)
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    
    
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math

input = sys.stdin.readline
N=int(input())
A = [int(input()) for i in range(N)]
mod = 998244353

S = sum(A)
maxA = max(A)
dp = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
dp[0][S-math.ceil(S/2)]=1
for i in range(1,N+1):
  for j in range(S+1-math.ceil(S/2)):
    dp[i][j] = (dp[i-1][j+A[i-1]]*2 + dp[i-1][j])%mod
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0]*(S+1+maxA-math.ceil(S/2)) for j in range(N+1)]
  dp2[0][S-math.ceil(S/2)]=1
  for i in range(1,N+1):
    for j in range(S+1-math.ceil(S/2)):
      dp2[i][j] = (dp2[i-1][j+A[i-1]] + dp2[i-1][j])%mod
  bad_rg = dp2[N][0]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%mod)

Solution (Python):
n = int(input())
alist = []
for i in range(n):
    alist.append(int(input()))
mod = 998244353
asum = sum(alist)


asum_half = (asum + 1) // 2
dp = [[0] * (asum_half + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(asum_half + 1):
        inext = i + 1
        dp[inext][j] = (dp[inext][j] + dp[i][j] * 2) % mod
        jsum = min(j + alist[i], asum_half)
        dp[inext][jsum] = (dp[inext][jsum] + dp[i][j]) % mod
dp_sum = dp[n][asum_half] % mod
dp_sum *= 3
dp_sum = dp_sum % mod


dp_dup = [[0] * (asum_half + 1) for _ in range(n + 1)]
dp_dup[0][0] = 1
if asum % 2 == 0:
    for i in range(n):
        for j in range(asum_half + 1):
            inext = i + 1
            dp_dup[inext][j] = (dp_dup[inext][j] + dp_dup[i][j]) % mod
            jsum = j + alist[i]
            if jsum > asum_half:
                continue
            dp_dup[inext][jsum] = (dp_dup[inext][jsum] + dp_dup[i][j]) % mod
dp_dup_sum = dp_dup[n][asum_half]
dp_dup_sum *= 3
dp_dup_sum = dp_dup_sum % mod


ans = pow(3, n, mod)
ans -= dp_sum
ans += dp_dup_sum

print(ans % mod)

Solution (Python):
import numpy as np

MOD=998244353
N=int(input())
A=np.array([int(input()) for _ in range(N)])
TOTAL=pow(3,N,MOD)
ASum=sum(A)
sumEnd=0
sumEnd=ASum//2+1

dp=np.array([0 for _ in range(sumEnd)],dtype=np.int64)
dp[0] = 1

for n in range(N):
	dp[A[n]:] += dp[:-A[n]]*2 % MOD

plus = 0
if ASum % 2 == 0:
	
	dpOther=np.array([0 for _ in range(sumEnd+1)],dtype=np.int64)
	dpOther[0] = 1
	for n in range(N):
		dpOther[A[n]:] += dpOther[:-A[n]] % MOD
	plus = (dpOther[ASum//2]*3) % MOD

exceptCnt=0
for s in range(0,sumEnd):
	exceptCnt = (exceptCnt + dp[s]*3) % MOD

exceptCnt -= plus
print((TOTAL - exceptCnt) % MOD )

Solution (Python):
import math
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)
m = 998244353
dp1 = np.zeros((N+1, s+1), dtype=np.int64)
dp1[0, 0] = 1
dp2 = np.zeros((N+1, s//2+1), dtype=np.int64)
dp2[0, 0] = 1
for i, ai in enumerate(a):
    dp1[i+1, :]   += dp1[i, :] * 2 % m
    dp1[i+1, ai:] += dp1[i, :-ai]
    dp2[i+1, :]   += dp2[i, :] % m
    dp2[i+1, ai:] += dp2[i, :-ai]
subset1 = np.sum(dp1[N, math.ceil(s/2):])
subset2 = 0 if s % 2 == 1 else dp2[N, s//2]
print((3 ** N - 3 * subset1 + 3 * subset2) % m)

Solution (Python):
N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
MOD = 998244353


dp1 = [[0] * (S + 1) for _ in range(N + 1)]
dp1[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp1[t][r] += dp1[t - 1][r] * 2
        dp1[t][r] += dp1[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp1[t][r] %= MOD

dp2 = [[0] * (S + 1) for _ in range(N + 1)]
dp2[0][0] = 1

for t in range(1, N + 1):
    for r in range(S + 1):
        dp2[t][r] += dp2[t - 1][r]
        dp2[t][r] += dp2[t - 1][r - A[t - 1]] if r - A[t - 1] >= 0 else 0
        dp2[t][r] %= MOD

cnt = 0
for r in range((S + 1) // 2, S + 1):
    cnt += dp1[N][r]

ans = 3 ** N - 3 * cnt + (3 * (dp2[N][S // 2]) if S % 2 == 0 else 0)
ans %= MOD

print(ans)

Solution (Python):
import sys
import numpy as np

def main():
    input = sys.stdin.readline
    N = int(input())
    A = [int(input()) for _ in range(N)]
    MOD = 998244353

    S = sum(A)
    a = A[0]
    
    
    
    dp0 = np.zeros((N, S+1), dtype=np.int64)
    dp0[0, a] = 1
    dp0[0, 0] = 2

    
    
    
    dp1 = np.zeros((N, S+1), dtype=np.int64)
    dp1[0, a] = 1
    dp1[0, 0] = 1
    for i in range(1, N):
        a = A[i]

        dp0[i, :] += dp0[i-1, :] * 2
        dp0[i, a:] += dp0[i-1, :-a]
        dp0[i, :] %= MOD

        dp1[i, :] += dp1[i-1, :]
        dp1[i, a:] += dp1[i-1, :-a]
        dp1[i, :] %= MOD


    ng = 0
    if S % 2 == 1:
        ng = np.sum(dp0[N-1, S//2 + 1:])
        ng = (ng * 3) % MOD

    else:
        ng = np.sum(dp0[N-1, S//2:])
        ng = (ng * 3 - dp1[N-1][S//2] * 3) % MOD

    ans = (pow(3, N, MOD) - ng) % MOD
    return ans


if __name__ == '__main__':
    print(main())

Solution (Python):

import sys
from collections import defaultdict
INF = float("inf")
MOD = 998244353  


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 = [[0]*(S+1) 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):     
        
        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][-(-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))  
    a = [int(next(tokens)) for _ in range(N)]  
    solve(N, a)


if __name__ == '__main__':
    main()

Solution (Python):
import math
import numpy as np

N = int(input())
A = np.array([int(input()) for _ in range(N)])
S = np.sum(A)
MOD = 998244353





dp0 = np.zeros((N + 1, S + 1), dtype=np.int64)






dp1 = np.zeros((N + 1, S // 2 + 1), dtype=np.int64)


dp0[0, 0] = 1
dp1[0, 0] = 1


for i, x in enumerate(A):

    
    
    dp0[i+1, :] += dp0[i, :] * 2 % MOD

    
    
    
    dp0[i+1, x:] += dp0[i, :-x]

    
    
    dp1[i+1, :] += dp1[i, :] % MOD

    
    dp1[i+1, x:] += dp1[i, :-x]



not_satisfy = np.sum(dp0[N][math.ceil(S/2):])


double_reduct = 0 if S % 2 == 1 else dp1[N][S/2]



ans = (3 ** N - 3 * not_satisfy + 3 * double_reduct) % MOD
print(ans)

Solution (Python):
import math

n = int(input())
a = [0]
mod = 998244353
p = pow(3, n, mod)

for i in range(0, n):
    a.append(int(input()))

s = sum(a)
hs = math.ceil(s / 2)
dp = [[0 for j in range(0, s + 1)] for i in range(0, n + 1)]
dp[0][0] = 1

for i in range(1, n + 1):
    for j in range(0, s + 1):
        dp[i][j] = (2 * dp[i - 1][j] + (0 if j - a[i] < 0 else dp[i - 1][j - a[i]])) % mod

p = (p - 3 * sum(dp[n][hs:])) % mod

if s % 2 == 0:
    for i in range(1, n + 1):
        for j in range(0, s // 2 + 1):
            dp[i][j] = (dp[i - 1][j] + (0 if j - a[i] < 0 else dp[i - 1][j - a[i]])) % mod

    p = (p + 3 * dp[n][hs]) % mod

print(p)

Solution (Python):
import math
import numpy as np

N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)

dp0 = np.zeros((N + 1, s + 1), dtype=np.int64)
dp0[0, 0] = 1
dp1 = np.zeros((N + 1, s // 2 + 1), dtype=np.int64)
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod


c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))

c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % mod
print(ans)

Solution (Python):
import math
import numpy as np

N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)


dp0 = np.zeros((N + 1, s + 1))
dp0[0, 0] = 1

dp1 = np.zeros((N + 1, s // 2 + 1))
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod

c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % mod
print(ans)

Solution (Python):

import numpy as np
N = int(input())
a = np.array([int(input()) for i in range(N)])
mod =998244353
sum_a = np.sum(a)
dp =  np.zeros((N+1,sum_a+1))
half_dp = np.zeros((N+1,sum_a//2+1))
dp[0][0], half_dp[0][0] = 1, 1

for i in range(1,N+1):
    dp[i,:] += dp[i-1,:]*2 % mod
    dp[i,a[i-1]:] +=  dp[i-1, :-a[i-1]] % mod
    half_dp[i,:] +=  half_dp[i-1,:] % mod
    half_dp[i,a[i-1]:] += half_dp[i-1,:-a[i-1]] % mod

all_combination = 3**N % mod
half_sum_a = (sum_a //2) if sum_a % 2 == 0 else (sum_a//2)+1 
p = np.sum(dp[N][half_sum_a:])
c = half_dp[N][half_sum_a] if sum_a % 2==0 else 0
print(int(all_combination - 3 * p + 3 * c) % mod)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
import numpy as np

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 998244353

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-1)/2) ** 2 * x % mod

N = INT()
a = np.array([INT() for _ in range(N)])

sum_a = np.sum(a)
dp = np.zeros((N+1, sum_a+1))
dp[0][0] = 1

dp2 = np.zeros((N+1, sum_a//2+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] += dp[i, :]*2 % mod 
	dp[i+1, x:] += dp[i, :-x] % mod 
	dp2[i+1,:] += dp2[i, :] % mod
	dp2[i+1, x:] += dp2[i, :-x] % mod


if sum_a%2 == 0:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))

Solution (Python):
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)

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

s = sum(a)
mod = 998244353

dp1 = [0] * (s+1)
dp2 = [0] * (s+1)
dp1[0] = 1
dp2[0] = 1
sum_ = 0


ans = 0
for n in range(N):
    for i in reversed(range(sum_+1)):
        dp1[i] %= mod
        dp2[i] %= mod
        dp1[i+a[n]] += dp1[i]
        dp1[i] <<= 1
        dp2[i+a[n]] += dp2[i]
    
    sum_ += a[n]

ans = (3 ** N)%mod
for i in range(s+1):
    if i*2 >= s:
        ans -= dp1[i]*3 + mod*3
        ans %= mod
    if i*2 == s:
        ans += dp2[i]*3
        ans %= mod

print(ans)

Solution (Python):
def solve():
    mod=998244353
    N=int(input())
    A=[]
    for i in range(N):
        A.append(int(input()))
    sumA=sum(A)
    sumA2=(sumA+1)//2

    dp = [[0]*(sumA2+2) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in range(sumA2+1):
            if dp[i][j]!=0:
                dp[i+1][j]=(dp[i+1][j]+dp[i][j]*2)%mod
                j2=min(sumA2,j+A[i])
                dp[i+1][j2]=(dp[i+1][j2]+dp[i][j])%mod
    ans=1
    for i in range(N):
        ans=(ans*3)%mod
    ans=(ans+mod-3*dp[N][sumA2])%mod

    if sumA%2==0:
        dp = [[0]*(sumA2+2) for i in range(N+1)]
        dp[0][0]=1
        for i in range(N):
            for j in range(sumA2+2):
                if dp[i][j]!=0:
                    dp[i+1][j]+=dp[i][j]
                    j2=min(sumA2+1,j+A[i])
                    dp[i+1][j2]+=dp[i][j]
        ans=(ans+3*dp[N][sumA2])%mod

    return ans

print(solve())

Solution (Python):
import numpy as np
N = int(input())
a = np.array([int(input()) for i in range(N)])
MOD =998244353
sum_a = np.sum(a)
dp =  np.zeros((N+1,sum_a+1))
half_dp = np.zeros((N+1,sum_a//2+1))
dp[0][0] = 1
half_dp[0][0] = 1

for i in range(1,N+1):
    dp[i,:] += dp[i-1,:]*2 %MOD
    dp[i,a[i-1]:] +=  dp[i-1, :-a[i-1]]%MOD
    half_dp[i,:] +=  half_dp[i-1,:] %MOD
    half_dp[i,a[i-1]:] += half_dp[i-1,:-a[i-1]]%MOD

all_combination = 3**N %MOD
half_sum_a = sum_a //2 if sum_a %2 == 0 else sum_a//2+1 
bigger_than_half = np.sum(dp[N][half_sum_a:])
half_half = half_dp[N][half_sum_a] if sum_a%2==0 else 0
ans = int(all_combination - 3* bigger_than_half + 3* half_half)%MOD
print(ans)

Solution (Python):
MOD = 998244353
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_sum = sum(a)
half = int(a_sum / 2)

dp = [[0] * (a_sum + 1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    ni = i+1
    for j in range(a_sum+1):
        if dp[i][j] != 0:
            dp[ni][j] += (dp[i][j] * 2) % MOD
            dp[ni][j+a[i]] += dp[i][j]
ans = pow(3, n, MOD)
for item in dp[n][half:]:
    ans -= item * 3
    ans %= MOD

if a_sum % 2 == 0:
    dp = [[0] * (half + 1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        ni = i+1
        for j in range(half+1):
            dp[ni][j] += dp[i][j] % MOD
            if j+a[i] < half+1:
                dp[ni][j+a[i]] += dp[i][j] % MOD
ans += dp[n][half] * 3
ans %= MOD
if ans < 0:
    ans += MOD
print(ans)

Solution (Python):
import math

N = int(input())
LI = []
for a in range(N):
    LI.append(int(input()))

MOD = 998244353
SUM = sum(LI)


dp = [[0 for _ in range(SUM + 1)] for _ in range(len(LI))]
dp[0][0] = 2  
dp[0][LI[0]] = 1
for t in range(1, len(LI)):
    for r in range(len(dp[t])):
        dp[t][r] += dp[t - 1][r] * 2 % MOD
        dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0


ans = (3 ** len(LI)) % MOD


ans -= sum([dp[-1][r] for r in range(math.ceil(SUM / 2), SUM + 1)]) * 3
ans %= MOD

if SUM % 2 == 0:
    
    
    dp = [[0 for _ in range(SUM // 2 + 1)] for _ in range(len(LI))]
    dp[0][0] = 1  
    dp[0][LI[0]] = 1
    for t in range(1, len(LI)):
        for r in range(len(dp[t])):
            dp[t][r] += dp[t - 1][r] % MOD
            dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0
    
    ans += dp[-1][SUM // 2] * 3
    ans %= MOD

print(ans)