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



Sample input:
4
1
1
1
2


Sample output:
18

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a_ls = []
for i in range(N):
    a_ls.append(int(input()))
S = sum(a_ls)
memo_ls = [[1 if i == 0 else 0 for i in range(N * 300 + 1)] for j in range(N+1)]
memo_ls2 = [[1 if i == 0 else 0 for i in range(N * 300 + 1)] for j in range(N+1)]
cnt = 0
sp_cnt = 0
for i in range(1,N+1):
    for j in range(N * 300 + 1):
        if j - a_ls[i-1] >= 0:
            memo_ls[i][j] = memo_ls[i-1][j - a_ls[i-1]] + memo_ls[i-1][j] * 2
            memo_ls2[i][j] = memo_ls2[i - 1][j - a_ls[i - 1]] + memo_ls2[i - 1][j]
        else:
            memo_ls[i][j] = memo_ls[i - 1][j] * 2
            memo_ls2[i][j] = memo_ls2[i - 1][j]
        memo_ls[i][j] %= 998244353
        memo_ls2[i][j] %= 998244353
        if i == N and j >= S / 2:
            cnt += memo_ls[i][j]
        if i == N and j == S / 2:
            sp_cnt += memo_ls2[i][j]

print((3 ** N - cnt * 3 + sp_cnt * 3) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import math

MOD = 998244353

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

S = sum(a)

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

for i, x in enumerate(a):
  for j in range(S):
    dp1[i+1][j] += dp1[i][j] * 2 % MOD
    dp2[i+1][j] += dp2[i][j] % MOD
  for j in range(x, S+1):
    dp1[i+1][j] += dp1[i][j-x] % MOD
    dp2[i+1][j] += dp2[i][j-x] % MOD
    
# 全塗り分けパターン
pat = 3 ** N % MOD
# 最大の色の値が S/2 以上のパターン（三角形ができない）
s1  = 3 * sum(dp1[N][math.ceil(S / 2):]) % MOD
# 最大の色の値が S/2 に等しいパターン（重複している）
s2  = 3 * dp2[N][S // 2] % MOD if S % 2 == 0 else 0

print(int(pat - s1 + s2) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

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

# Calculate counts of (R >= s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    for j in range(s + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            dp[i][j] = dp[i - 1][j] * 2 + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0)
c0 = sum(dp[N][math.ceil(s / 2):s+2])

# Calculate counts of (R == s / 2 and G == s / 2)
dp = [[0 for _ in range(s // 2 + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    for j in range(s // 2 + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            dp[i][j] = dp[i - 1][j] + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0)
c1 = dp[N][s // 2] if s % 2 == 0 else 0

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import numpy as np
import math

MOD = 998244353

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

S = sum(a)

dp1 = np.zeros((N + 1, S + 1))
dp1[0, 0] = 1
dp2 = np.zeros((N + 1, S + 1))
dp2[0, 0] = 1

for i, x in enumerate(a):
  ## 長さを計算する色をcとして、cの長さに対する組み合わせを数える
  dp1[i+1, :]  += dp1[i, :] * 2 % MOD  # c以外に塗り分ける場合（各2通り追加）
  dp1[i+1, x:] += dp1[i, :-x]   % MOD  # cに塗る場合（xずらしたところに1通り追加）
  ## 2色だけを使う組み合わせを数える
  dp2[i+1, :]  += dp2[i, :]     % MOD  # cではないいずれか1色に塗る場合（各1通り）
  dp2[i+1, x:] += dp2[i, :-x]   % MOD  # cに塗る場合
  
# 全塗り分けパターン
pat = 3 ** N % MOD
# 最大の色の値が S/2 以上のパターン（三角形ができない）
s1  = 3 * sum(dp1[N, math.ceil(S / 2):]) % MOD
# 最大の色の値が S/2 に等しいパターン（重複している）
s2  = 3 * dp2[N, S // 2] % MOD if S % 2 == 0 else 0

print(int(pat - s1 + s2) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np

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

# Counts of (R >= s / 2)
dp0 = np.zeros((N + 1, s + 1))
dp0[0, 0] = 1
# Counts of (R == s / 2 and G == s / 2)
dp1 = np.zeros((N + 1, s + 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) % 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

n,*ms = map(int,sys.stdin.read().split())

total=sum(ms)
dp=[0]*(total+1)
dp[0]=1

for m in ms:
    for i in range(total,m-1,-1):
        dp[i]=dp[i]*2+dp[i-m]
    for i in range(m):
        dp[i]*=2

border = (total + 1) // 2
yo=sum(dp[border:])*3

if total%2==0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    for m in ms:
        for i in range(-1, m - total // 2 - 2, -1):
            dp2[i] += dp2[i - m]
    yo-=dp2[-1]*3

print((3**n-yo)%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(sys.stdin.readline())
ms = []
for i in range(n):
    ms += [int(sys.stdin.readline())]

total=sum(ms)
dp=[0]*(total+1)
dp[0]=1

for m in ms:
    for i in range(total,m-1,-1):
        dp[i]=dp[i]*2+dp[i-m]
    for i in range(m):
        dp[i]*=2

border = (total + 1) // 2
yo=sum(dp[border:])*3

if total%2==0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    for m in ms:
        for i in range(-1, m - total // 2 - 2, -1):
            dp2[i] += dp2[i - m]
    yo-=dp2[-1]*3

print((3**n-yo)%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

def way(moku, wa, cur):
    if wa==moku:
        return 1
    if cur == n or wa > moku:
        return 0
    re1 = way(moku, wa + ms[cur], cur + 1)
    re2 = way(moku, wa, cur + 1)
    return re1 + re2

n = int(sys.stdin.readline())
ms = []
for i in range(n):
    ms += [int(sys.stdin.readline())]

total=sum(ms)
dp=[0]*(total+1)
dp[0]=1
for m in ms:
    for i in range(total,m-1,-1):
        dp[i]=dp[i]*2+dp[i-m]
    for i in range(m):
        dp[i]*=2

border = (total + 1) // 2
yo=sum(dp[border:])*3
if total%2==0:
    yo-=way(total//2,0,0)*3
print((3**n-yo)%998244353)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

s = sum(a)

dp = [[0 for j in range(s+1)] for i in range(n+1)]
dp[0][0] = 1
dp2 = [[0 for j in range(s+1)] for i in range(n+1)]
dp2[0][0] = 1

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

ans = 3 ** n
for elem in dp[n][(s+1)//2:s+1]:
    ans -= elem*3

if s%2==0:
    ans += dp2[n][s//2] * 3

print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))

s = sum(a)

dp = [[0 for j in range(s+1)] for i in range(n+1)]
dp[0][0] = 1

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

ans = 3 ** n
for elem in dp[n][(s+1)//2:s+1]:
    ans -= elem*3

dp2 = [[0 for j in range(s+1)] for i in range(n+1)]
dp2[0][0] = 1

if s%2==0:
    for i in range(1,n+1):
        for j in range(s+1):
            if j+a[i-1] <= s:
                dp2[i][j+a[i-1]] += dp2[i-1][j]
            dp2[i][j] += dp2[i-1][j]
    ans += dp2[n][s//2] * 3

print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
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

def sum_dp(l):
	tmp = 0
	for i, x in enumerate(l[N]):
		if i >= sum_a/2:
			tmp = (tmp + x)%mod
	return tmp

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+1))
dp2[0][0] = 1

for i, x in enumerate(a):
	dp[i+1, :] = (dp[i+1, :] + dp[i, :]*2)%mod # 赤以外に塗り分ける
	dp[i+1, x:] = (dp[i+1, x:] + dp[i, :-x])%mod # 赤に塗り分ける
	dp2[i+1,:] = (dp2[i+1, :] + dp2[i, :])%mod
	dp2[i+1, x:] = (dp2[i+1, x:] + dp2[i, :-x])%mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2:])+3*dp2[N,sum_a//2])%mod))
else:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)
	print(int((power(3, N)-3*np.sum(dp[N,sum_a//2+1:]))%mod))

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
a = []
s = 0
for _ in range(N):
    a_i = int(input())
    a.append(a_i)
    s += a_i

# Calculate counts of (R >= s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    for j in range(s + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            dp[i][j] = dp[i - 1][j] * 2 + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0)
c0 = sum(dp[N][math.ceil(s / 2):s+2])

# Calculate counts of (R == s / 2 and G == s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]
for i in range(N + 1):
    for j in range(s + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            dp[i][j] = dp[i - 1][j] + (dp[i - 1][j - a[i - 1]] if j >= a[i - 1] else 0)
c1 = dp[N][s // 2] if s % 2 == 0 else 0

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

Submission status: Time Limit Exceeded

Solution code:
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

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

def sum_dp(l):
	tmp = 0
	for i, x in enumerate(l[N]):
		if i >= sum_a/2:
			tmp = (tmp + x)%mod
	return tmp

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

sum_a = sum(a)
dp = [[0]*(sum_a+1) for _ in range(N+1)]
dp[0][0] = 1

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

for i, x in enumerate(a):
	for j in range(sum_a+1):
		if j+x >= sum_a+1:
			continue
		dp[i+1][j] = (dp[i+1][j] + dp[i][j]*2)%mod # 赤以外に塗り分ける
		dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j])%mod # 赤に塗り分ける
		dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j])%mod
		dp2[i+1][j+x] = (dp2[i+1][j+x] + dp2[i][j])%mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
	print((power(3, N)-3*sum_dp(dp)+3*dp2[N][sum_a//2])%mod)
else:
	# print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)
	print((power(3, N)-3*sum_dp(dp))%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

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

memo = np.full(((n+1), (n * max(aa) + 1), 2), -1, dtype=np.int64)
def dfs12(i, c):
    if 0 <= memo[i, c, 0]:
        return memo[i, c]

    if i == n:
        memo[i, c, 0] = 3 if total <= (2 * c) else 0
        memo[i, c, 1] = 3 if total == (2 * c) else 0
        return memo[i, c]

    v0 = dfs12(i + 1, c)
    v1 = dfs12(i + 1, c + aa[i])

    memo[i, c, 0] = (2 * v0[0] + v1[0])
    memo[i, c, 1] = (v0[1] + v1[1])
    return memo[i, c]

a, b = dfs12(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())

a = []
s = 0
for _ in range(N):
    a_i = int(input())
    a.append(a_i)
    s += a_i

# Calculate counts of (R >= s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]

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

c0 = 0
for j in range(math.ceil(s / 2), s + 1):
    c0 += dp[N][j]

# Calculate counts of (R == s / 2 and G == s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]

for i in range(N + 1):
    for j in range(s + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            if j - a[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]]

c1 = 0
if s % 2 == 0:
    c1 = dp[N][s // 2]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

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

memo = np.full(((n+1), (n * max(aa) + 1), 2), -1, dtype=np.int32)
def dfs(i, c):
    if 0 <= memo[i, c, 0]:
        return memo[i, c]

    if i == n:
        memo[i, c, 0] = 3 if total <= (2 * c) else 0
        memo[i, c, 1] = 3 if total == (2 * c) else 0
        return memo[i, c]

    v0, v1 = dfs(i + 1, c)
    v2, v3 = dfs(i + 1, c + aa[i])

    acc0 = (v0 + v0) % 998244353
    acc0 = (acc0 + v2) % 998244353
    memo[i, c, 0] = acc0

    memo[i, c, 1] = (v1 + v3) % 998244353
    return memo[i, c]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

Submission status: Time Limit Exceeded

Solution code:
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

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 = [INT() for _ in range(N)]

sum_a = sum(a)
dp = [[0]*(sum_a+1) for _ in range(N+1)]
dp[0][0] = 1

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

for i, x in enumerate(a):
	for j in range(sum_a+1):
		if j+x >= sum_a+1:
			continue
		dp[i+1][j] = (dp[i+1][j] + dp[i][j]*2)%mod # 赤以外に塗り分ける
		dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j])%mod # 赤に塗り分ける
		dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j])%mod
		dp2[i+1][j+x] = (dp2[i+1][j+x] + dp2[i][j])%mod
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
else:
	print((power(3, N)-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)

Submission status: Time Limit Exceeded

Solution code:
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

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 = [INT() for _ in range(N)]

sum_a = sum(a)
dp = [[0]*(sum_a+1) for _ in range(N+1)]
dp[0][0] = 1

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

for i, x in enumerate(a):
	for j in range(sum_a+1):
		if j+x >= sum_a+1:
			continue
		dp[i+1][j] = (dp[i+1][j] + dp[i][j]*2) # 赤以外に塗り分ける
		dp[i+1][j+x] = (dp[i+1][j+x] + dp[i][j]) # 赤に塗り分ける
		dp2[i+1][j] += dp2[i][j]
		dp2[i+1][j+x] += dp2[i][j]
# print(dp)
# print(dp2)
if sum_a%2 == 0:
	print((3**N-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2])+3*dp2[N][sum_a//2])%mod)
else:
	print((3**N-3*sum([dp[N][i] for i in range(sum_a+1) if i >= sum_a//2+1]))%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

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

memo = np.full(((n+1), (n * max(aa) + 1), 2), -1, dtype=np.int64)
def dfs12(i, c):
    if 0 <= memo[i, c, 0]:
        return memo[i, c]

    if i == n:
        memo[i, c, 0] = 3 if total <= (2 * c) else 0
        memo[i, c, 1] = 3 if total == (2 * c) else 0
        return memo[i, c]

    v0 = dfs12(i + 1, c)
    v1 = dfs12(i + 1, c + aa[i])

    memo[i, c, 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[i, c, 1] = (v0[1] + v1[1]) % 998244353
    return memo[i, c]

a, b = dfs12(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

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

memo = np.full(((n+1), (n * max(aa) + 1)), -1, dtype=np.int64)
def dfs0(i, c):
    if 0 <= memo[i, c]:
        return memo[i, c]

    if i == len(aa):
        memo[i, c] = 3 if total <= (2 * c) else 0
        return memo[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo[i, c] = acc
    return memo[i, c]

def dfs1(i, c):
    if 0 <= memo[i, c]:
        return memo[i, c]

    if i == len(aa):
        memo[i, c] = 3 if total == (2 * c) else 0
        return memo[i, c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo[i, c] = acc
    return memo[i, c]

ret = (ret - dfs0(0, 0)) % 998244353
memo.fill(-1)
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

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

memo0 = np.zeros(((n+1), (n * max(aa) + 1)), dtype=np.int64)
memo0[:] = -1
def dfs0(i, c):
    if 0 <= memo0[i, c]:
        return memo0[i, c]

    if i == len(aa):
        memo0[i, c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i, c] = acc
    return memo0[i, c]

memo1 = np.zeros(((n+1), (n * max(aa) + 1)), dtype=np.int64)
memo1[:] = -1
def dfs1(i, c):
    if 0 <= memo1[i, c]:
        return memo1[i, c]

    if i == len(aa):
        memo1[i, c] = 3 if total == (2 * c) else 0
        return memo1[i, c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo1[i, c] = acc
    return memo1[i, c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

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

memo0 = [[-1] * (n * max(aa) + 1) for _ in range(n + 1)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * (n * max(aa) + 1) for _ in range(n + 1)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo1[i][c] = acc
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import collections

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[N][sum] : N個目までの合計がsumの数
    dp = [collections.defaultdict(int) for i in range(N+1)]
    dp[0][0]=1
    for i in range(N):
        for j in dp[i].keys():
            if dp[i][j]==0:
                continue
            dp[i+1][j]+=dp[i][j]*2
            j2=min(sumA2,j+A[i])
            dp[i+1][j2]+=dp[i][j]
    ans=1
    for i in range(N):
        ans=(ans*3)%mod
    ans=(ans+mod-3*dp[N][sumA2])%mod

    if sumA%2==0:
        # dp[N][sum] : N個目までの合計がsumの数
        dp = [collections.defaultdict(int) for i in range(N+1)]
        dp[0][0]=1
        for i in range(N):
            for j in dp[i].keys():
                if dp[i][j]==0:
                    continue
                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())

Submission status: Time Limit Exceeded

Solution code:
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+1))
dp[0][0] = 1
half_dp[0][0] = 1


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


all_combination = 1
for i in range(N):
    all_combination = (all_combination*3) %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)

Submission status: Time Limit Exceeded

Solution code:
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[N][sum] : N個目までの合計がsumの数
    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:
                continue
            dp[i+1][j]+=dp[i][j]*2
            j2=min(sumA2,j+A[i])
            dp[i+1][j2]+=dp[i][j]
    ans=1
    for i in range(N):
        ans=(ans*3)%mod
    ans=(ans+mod-3*dp[N][sumA2])%mod

    if sumA%2==0:
        # dp[N][sum] : N個目までの合計がsumの数
        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:
                    continue
                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())

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def get_input():
    N = int(input())
    a = [int(input()) for i in range(N)]
    return N,a

MOD =998244353
def solve(N,a):
    sum_a = sum(a)
    dp = np.zeros((N+1,sum_a+1))
    dp[0][0] = 1
    for j in range(1,N+1):
        dp[j][0] = (2 * dp[j-1][0])%MOD

    for i in range(1,N+1):
        for j in range(1,sum_a+1):
            if j-a[i-1]>=0:
                dp[i][j] = ( dp[i][j] + dp[i-1][j]*2 +dp[i-1][j-a[i-1]])%MOD
            else:
                dp[i][j] = ( dp[i][j] + dp[i-1][j]*2 )%MOD
    all_combination = 1
    for i in range(N):
        all_combination = (all_combination*3) %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:])
    if sum_a %2 == 0:
        half_dp = np.zeros((N+1,sum_a+1))
        half_dp[:,0] = 1
        for i in range(1,N+1):
            for j in range(1,sum_a+1):
                if j-a[i-1]>=0:
                    half_dp[i][j] = ( half_dp[i][j] + half_dp[i-1][j] +half_dp[i-1][j-a[i-1]])%MOD
                else:
                    half_dp[i][j] = ( half_dp[i][j] + half_dp[i-1][j] )%MOD
        half_half = half_dp[N][half_sum_a]
        
    else:
        half_half = 0
    return int(all_combination - 3* bigger_than_half + 3* half_half)%MOD

    
if __name__ =="__main__":
    N,a = get_input()
    ans = solve(N,a)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-


def solve():
    MOD = 998244353
    N = int(input())
    A = []
    for i in range(N):
        A.append(int(input()))
    

    def dfs(depth, r, g, b):
        """ 個数を返す """
        if depth == N:
            if min(r,g,b) == 0:
                return 0
            else:
                longest = max(r,g,b)
                other = (r+g+b) - longest
                if longest < other:
                    return 1
                else:
                    return 0
        
        ret1 = dfs(depth+1, r+A[depth], g, b)
        ret2 = dfs(depth+1, r, g+A[depth], b)
        ret3 = dfs(depth+1, r, g, b+A[depth])

        return (ret1+ret2+ret3)%MOD
    
    ans = dfs(0, 0, 0, 0)
    print(ans)

    


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
A = [int(input()) for _ in range(n)]

# n = 4
# A = [1,1,1,2]

M = sum(A)

def half_half_zero_case():
    if M % 2 != 0:
        return 0
    else:
        dp = [[0] * (M + 1) for i in range(n + 1)]
        dp[0][0] = 1

        for i in range(n):
            for j in range(M):
                if dp[i][j] > 0:
                    dp[i + 1][j] += dp[i][j]
                    dp[i + 1][j + A[i]] += dp[i][j]
        
        return dp[n][int(M / 2)]


def r_gte_half_case():
    dp = [[0] * (M + 1) for i in range(n + 1)]
    dp[0][0] = 1

    for i in range(n):
        for j in range(M):
            if dp[i][j] > 0:
                dp[i + 1][j] += 2 * dp[i][j]
                dp[i + 1][j + A[i]] += dp[i][j]

    return sum(dp[n][math.ceil(M / 2) : ])

def all_case():
    return 3**n

result = all_case() - 3 * (r_gte_half_case() - half_half_zero_case())
print(result % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
	N = int(input())
	A = [0]*N
	for i in range(N):
		A[i] = int(input())

	memo = dict()
	def create_triangles(r, g, b, num):
		ans = 0
		if num == N:
			if (abs(b-g)<r and r<b+g) or (abs(b-r)<g and g<b+r) or (abs(r-g)<b and b<r+g):
				return 1
			else:
				return 0
		if not (r+A[num],g,b) in memo:
			tmp = create_triangles(r+A[num], g, b, num+1)
			memo[(r+A[num],g,b)] = tmp
			memo[(r+A[num],b,g)] = tmp
			memo[(b,r+A[num],g)] = tmp
			memo[(b,g,r+A[num])] = tmp
			memo[(g,r+A[num],b)] = tmp
			memo[(g,b,r+A[num])] = tmp
		ans += memo[(r+A[num],g,b)]
		ans %= 998244353

		if not (r,g+A[num],b) in memo:
			tmp = create_triangles(r, g+A[num], b, num+1)
			memo[(r,g+A[num],b)] = tmp
			memo[(r,b,g+A[num])] = tmp
			memo[(b,r,g+A[num])] = tmp
			memo[(b,g+A[num],r)] = tmp
			memo[(g+A[num],r,b)] = tmp
			memo[(g+A[num],b,r)] = tmp
		ans += memo[(r,g+A[num],b)]
		ans %= 998244353

		if not (r,g,b+A[num]) in memo:
			tmp = create_triangles(r, g, b+A[num], num+1)
			memo[(r,g,b+A[num])] = tmp
			memo[(r,b+A[num],g)] = tmp
			memo[(b+A[num],r,g)] = tmp
			memo[(b+A[num],g,r)] = tmp
			memo[(g,r,b+A[num])] = tmp
			memo[(g,b+A[num],r)] = tmp
		ans += memo[(r,g,b+A[num])]
		ans %= 998244353

		return ans

	ans = create_triangles(0,0,0,0)
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from copy import copy

n = int(input())
A = [int(input()) for _ in range(n)]
M = sum(A)

def half_half_zero_case():
    if M % 2 != 0:
        return 0
    else:
        counter = Counter({0: 1})
        for i in range(n):
            counter_new = Counter()
            for key in counter:
                counter_new[key] += counter[key]
                counter_new[key + A[i]] += counter[key]
            counter = counter_new
        
        return counter[M/2]


def r_gte_half_case():
    counter = Counter({0: 1})
    for i in range(n):
        counter_new = Counter()
        for key in counter:
            counter_new[key] += 2 * counter[key]
            counter_new[key + A[i]] += counter[key]
        counter = counter_new

    result = 0
    for key in counter:
        if key >= M / 2:
            result += counter[key]
    
    return result


def all_case():
    return 3**n


result = all_case() - 3 * (r_gte_half_case() - half_half_zero_case())
print(result % 998244353)