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())
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)

Submission status: Time Limit Exceeded

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


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


dp_dup = [[0] * (asum + 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 // 2 + 1):
            dp_dup[i+1][j] = (dp_dup[i+1][j] + dp_dup[i][j]) % mod
            jsum = j + alist[i]
            if jsum > asum:
                continue
            dp_dup[i+1][jsum] = (dp_dup[i+1][jsum] + dp_dup[i][j]) % mod
dp_dup_sum = dp_dup[n][(asum+1)//2]
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)

Submission status: Time Limit Exceeded

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


dp = [[0] * (asum + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(asum + 1):
        dp[i+1][j] = (dp[i+1][j] + dp[i][j] * 2) % mod
        jsum = j + alist[i]
        if jsum > asum:
            continue
        dp[i+1][jsum] = (dp[i+1][jsum] + dp[i][j]) % mod
dp_sum = sum(dp[n][((asum+1)//2):]) % mod
dp_sum *= 3
dp_sum = dp_sum % mod

dp_dup = [[0] * (asum + 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 // 2 + 1):
            dp_dup[i+1][j] = (dp_dup[i+1][j] + dp_dup[i][j]) % mod
            jsum = j + alist[i]
            if jsum > asum:
                continue
            dp_dup[i+1][jsum] = (dp_dup[i+1][jsum] + dp_dup[i][j]) % mod
dp_dup_sum = dp_dup[n][(asum+1)//2]
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)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
alist = [int(input()) for i in range(N)]
### 三角形が成立しない場合を数える
MOD = 998244353
S = sum(alist)
Sharf = S / 2

#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = [{} for i in range(N+1)]
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = [{} for i in range(N+1)]

def ddp(cur_N, R): #(retA: R>=S/2となる数, retB: R=G=S/2,B=0の数)を返す
    if R in dptableA[cur_N]: #DPテーブルにある
        return dptableA[cur_N][R], dptableB[cur_N][R]
    if cur_N == N: #末端
        retA = 1 if R >= Sharf else 0
        retB = 1 if R == Sharf else 0
        return retA, retB
    if R >= Sharf: #R>=S/2はこれ以降のパターン全てR>=S/2
        #となるので残りの要素をRGBどこに割り振っても良い
        retA = pow(3, N-cur_N, MOD)
        retB = 1 if R == Sharf else 0 #特にR=S/2の時はR=G=S/2にできる
        return retA, retB
    
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retA_R, retB_R = ddp(cur_N+1, R+ai) #Rに振り分けた場合
    retA_GB, retB_GB = ddp(cur_N+1,R) #Rに入れなかった場合
    retA_GB = retA_GB * 2 %MOD #GBで2通りあるので2倍
    retA = (retA_R + retA_GB) % MOD
    retB = (retB_R + retB_GB) % MOD
    dptableA[cur_N][R] = retA
    dptableB[cur_N][R] = retB
    return retA, retB

retA, retB = ddp(0,0)
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
alist = [int(input()) for i in range(N)]
### 三角形が成立しない場合を数える
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

tbsize = int(Sharf//1)+1
#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = [{} for i in range(N+1)]
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = [{} for i in range(N+1)]

def ddp(cur_N, R): #(retA: R>=S/2となる数, retB: R=G=S/2,B=0の数)を返す
    if R in dptableA[cur_N]: #DPテーブルにある
        return dptableA[cur_N][R], dptableB[cur_N][R]
    if cur_N == N: #末端
        retA = 1 if R >= Sharf else 0
        retB = 1 if R == Sharf else 0
        return retA, retB
    if R >= Sharf: #R>=S/2はこれ以降のパターン全てR>=S/2
        #となるので残りの要素をRGBどこに割り振っても良い
        retA = pow(3, N-cur_N, MOD)
        retB = 1 if R == Sharf else 0 #特にR=S/2の時はR=G=S/2にできる
        return retA, retB
    if asum[cur_N] - R > Sharf: #Rに入れないものがS/2を超える
        return 0, 0 #どう頑張ってもR >= S/2を実現できない
    
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retA_R, retB_R = ddp(cur_N+1, R+ai) #Rに振り分けた場合
    retA_GB, retB_GB = ddp(cur_N+1,R) #Rに入れなかった場合
    retA_GB = retA_GB * 2 %MOD #GBで2通りあるので2倍
    retA = (retA_R + retA_GB) % MOD
    retB = (retB_R + retB_GB) % MOD
    dptableA[cur_N][R] = retA
    dptableB[cur_N][R] = retB
    return retA, retB

retA, retB = ddp(0,0)
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
alist = [int(input()) for i in range(N)]
### 三角形が成立しない場合を数える
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

tbsize = int(Sharf//1)+1
#dptableA[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
dptableA = [[0 for j  in range(tbsize)] for k in range(N)]
#dptableB[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptableB = [[0 for j  in range(tbsize)] for k in range(N)]
dpflag = [[False for j  in range(tbsize)] for k in range(N)]

def ddp(cur_N, R): #(retA: R>=S/2となる数, retB: R=G=S/2,B=0の数)を返す
    if cur_N == N: #末端
        retA = 1 if R >= Sharf else 0
        retB = 1 if R == Sharf else 0
        return retA, retB
    if R >= Sharf: #R>=S/2はこれ以降のパターン全てR>=S/2
        #となるので残りの要素をRGBどこに割り振っても良い
        retA = pow(3, N-cur_N, MOD)
        retB = 1 if R == Sharf else 0 #特にR=S/2の時はR=G=S/2にできる
        return retA, retB
    if asum[cur_N] - R > Sharf: #Rに入れないものがS/2を超える
        return 0, 0 #どう頑張ってもR >= S/2を実現できない
    if dpflag[cur_N][R]: #DPテーブルにある
        return dptableA[cur_N][R], dptableB[cur_N][R]
    
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retA_R, retB_R = ddp(cur_N+1, R+ai) #Rに振り分けた場合
    retA_GB, retB_GB = ddp(cur_N+1,R) #Rに入れなかった場合
    retA_GB = retA_GB * 2 %MOD #GBで2通りあるので2倍
    retA = (retA_R + retA_GB) % MOD
    retB = (retB_R + retB_GB) % MOD
    dpflag[cur_N][R] = True
    dptableA[cur_N][R] = retA
    dptableB[cur_N][R] = retB
    return retA, retB

retA, retB = ddp(0,0)
#全体 - (ある辺がS/2以上) + (2辺がS/2)
ans = (pow(3, N, MOD) - retA*3 + retB*3) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
alist = [int(input()) for i in range(N)]
### 三角形が成立しない場合を数える
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2

#dptable[i番目までは振り分けた][Rの合計] -> そこからR>=S/2となる数
tbsize = int(Sharf//1)+1
dptable = [[0 for j  in range(tbsize)] for k in range(N)]
dpflag = [[False for j  in range(tbsize)] for k in range(N)]
def ddpR(cur_N, R): #R>=S/2となる数
    if cur_N == N: #末端
        ret = 1 if R >= Sharf else 0
        return ret 
    if R >= Sharf: #R>=S/2はこれ以降のパターン全てR>=S/2
        #となるので残りの要素をRGBどこに割り振っても良い
        ret = pow(3, N-cur_N, MOD)
        return ret
    if asum[cur_N] - R > Sharf: #Rに入れないものがS/2を超える
        return 0 #どう頑張ってもR >= S/2を実現できない
    if dpflag[cur_N][R]: #DPテーブルにある
        return dptable[cur_N][R]
    
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retR = ddpR(cur_N+1, R+ai) #Rに振り分けた場合
    retGB = ddpR(cur_N+1,R) * 2 #Rに入れなかった場合, GBで2通りあるので2倍
    ret = (retR+retGB) % MOD
    dpflag[cur_N][R] = True
    dptable[cur_N][R] = ret
    return ret

#dptable2[i番目までは振り分けた][Rの合計] -> そこからR=G=S/2, B=0となる数
dptable2 = [[0 for j  in range(tbsize)] for k in range(N)]
dpflag2 = [[False for j  in range(tbsize)] for k in range(N)]
def ddpRG(cur_N, R): #R=G=S/2,B=0の場合
    if cur_N == N:
        return 1 if R==Sharf else 0
    if R == Sharf:
        return 1
    if (R > Sharf) or (asum[cur_N]-R > Sharf):
        return 0
    if dpflag2[cur_N][R]:
        return dptable2[cur_N][R]
    ai = alist[cur_N]
    retR = ddpRG(cur_N+1, R+ai)
    retG = ddpRG(cur_N+1,R)
    ret = (retR+retG) % MOD
    dpflag2[cur_N][R] = True
    dptable2[cur_N][R] = ret
    return ret
score = pow(3, N, MOD) - ddpR(0, 0)*3 + ddpRG(0, 0)*3
score = score % MOD
print(score)

Submission status: Time Limit Exceeded

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

TOTAL=pow(3,N,MOD)
ASum=sum(A)

dp=[0 for _ in range(ASum+1)]
dp[0] = 1

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

sumEnd=0
plus = 0
sumEnd=ASum//2+1

if ASum % 2 == 0:
	# 合計が偶数
	dpOther=[0 for _ in range(ASum+1)]
	dpOther[0] = 1
	for n in range(N):
		for e in range(ASum,A[n]-1,-1):
			dpOther[e] = dpOther[e] + dpOther[e-A[n]]
			dpOther[e] %= 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 )

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

if S%2 == 0:
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

Submission status: Time Limit Exceeded

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

TOTAL=pow(3,N,MOD)
ASum=sum(A)

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

dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

prev=0
current=1
curMax=A[0]

bEven = (ASum%2==0)

for n in range(1,N):
	curMax += A[n]
	current = n % 2
	prev = (n+1) % 2
	for e in range(curMax+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		while MOD < dp[current][e]:
			dp[current][e] -= MOD

		if bEven:
			dpOther[current][e] = dpOther[prev][e]
			if A[n] <= e:
				dpOther[current][e] += dpOther[prev][e-A[n]]
			while MOD < dpOther[current][e]:
				dpOther[current][e] -= MOD

sumStart = 0
plus = 0

if bEven:
	# 合計が偶数
	sumStart=ASum//2
	plus = (dpOther[current][ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Submission status: Time Limit Exceeded

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

TOTAL=pow(3,N,MOD)
ASum=sum(A)

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

dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

prev=0
current=1
curMax=A[0]
for n in range(1,N):
	curMax += A[n]
	current = n % 2
	prev = (n+1) % 2
	for e in range(curMax+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		dp[current][e] %= MOD

		if ASum %2 == 0:
			dpOther[current][e] = dpOther[prev][e]
			if A[n] <= e:
				dpOther[current][e] += dpOther[prev][e-A[n]]
			dpOther[current][e] %= MOD

sumStart = 0
plus = 0

if ASum % 2 == 0:
	# 合計が偶数
	sumStart=ASum//2
	plus = (dpOther[current][ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Submission status: Time Limit Exceeded

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

TOTAL=pow(3,N,MOD)
ASum=sum(A)
AMax=max(A)

dp=[[0 for _ in range(ASum+1)] for _ in range(2)]

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

prev=0
current=1
curMax=A[0]
for n in range(1,N):
	curMax += A[n]
	current = n % 2
	prev = (n+1) % 2
	for e in range(curMax+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		dp[current][e] %= MOD
sumStart = 0
plus = 0

if ASum % 2 == 0:
	# 合計が偶数
	sumStart=ASum//2
	dpOther=[0 for _ in range(ASum+1)]
	dpOther[0] = 1
	for n in range(N):
		for e in range(ASum//2,A[n]-1,-1):
			dpOther[e] = dpOther[e] + dpOther[e-A[n]]
			dpOther[e] %= MOD
	plus = (dpOther[ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

if S%2 == 0:
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

Submission status: Time Limit Exceeded

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

TOTAL=pow(3,N,MOD)
ASum=sum(A)
AMax=max(A)

dp=[[0 for _ in range(ASum+1)] for _ in range(2)]

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

prev=0
current=1
for n in range(1,N):
	current = n % 2
	prev = (n+1) % 2
	for e in range(ASum+1):
		dp[current][e] = dp[prev][e]*2
		if A[n] <= e:
			dp[current][e] += dp[prev][e-A[n]]
		dp[current][e] %= MOD
sumStart = 0
plus = 0

if ASum % 2 == 0:
	# 合計が偶数
	sumStart=ASum//2
	dpOther=[0 for _ in range(ASum+1)]
	dpOther[0] = 1
	for n in range(N):
		for e in range(ASum,A[n]-1,-1):
			dpOther[e] = dpOther[e] + dpOther[e-A[n]]
			dpOther[e] %= MOD
	plus = (dpOther[ASum//2]*3) % MOD
else:
	# 合計が奇数の場合、ceil
	sumStart=ASum//2+1

exceptCnt=0
for s in range(sumStart,ASum+1):
	exceptCnt = (exceptCnt + dp[current][s]*3) % MOD

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

if S%2 == 0:
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
import math

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

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

if S%2 == 0:  
  dp2 = [[0 for i in range(S+1)] for j in range(N+1)]
  dp2[0][0]=1
  for i in range(1,N+1):
    for j in range(S+1):
      if A[i-1] <= j:
        dp2[i][j] = dp2[i-1][j-A[i-1]] + dp2[i-1][j]
      else:
        dp2[i][j] = dp2[i-1][j]
  bad_rg = dp2[N][int(S/2)]
else:
  bad_rg = 0
  
ans = 3**N - bad_r*3 + bad_rg*3
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
alist = [int(input()) for i in range(N)]
MOD = 998244353

asum = [0] 
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
Sharf = S / 2
#dptable[i番目を振り分ける][Rの合計][Gの合計] -> そこから成立する三角形の数
tbsize = int(Sharf//1)+1
dptable = [[[0 for i in range(tbsize)] for j  in range(tbsize)] for k in range(N)]
dpflag = [[[False for i in range(tbsize)] for j  in range(tbsize)] for k in range(N)]

def ddp(cur_N, R, G):
    B = asum[cur_N] - R - G
    if cur_N == N: #末端
        return 1
    if dpflag[cur_N][R][G]: #DPテーブルにある
        return dptable[cur_N][R][G]
    #そうではない場合は計算が必要
    ai = alist[cur_N]
    #aiをRGBのどれかに振り分ける
    retR = 0 if (R+ai) >= Sharf else ddp(cur_N+1, R+ai, G) #Rに振り分ける, 三角形ができない場合は0
    retG = 0 if (G+ai) >= Sharf else ddp(cur_N+1, R, G+ai)
    retB = 0 if (B+ai) >= Sharf else ddp(cur_N+1, R, G)
    ret = (retR+retG+retB) % MOD
    #DPテーブルに記憶
    dpflag[cur_N][R][G] = True
    dptable[cur_N][R][G] = ret
    return ret
print(ddp(0, 0, 0))

Submission status: Time Limit Exceeded

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

# dp1 = [[0] * (N + 1) for _ in range(S + 1)]
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)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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


s = sum(a)

#dp[t][r]:0~t番目の整数を塗り分け、赤い整数の和がrであるような場合の数
dp = [[0 for i in range(s+1)] for i in range(n + 1)]
dp[0][0] = 1
dp0 = [[0 for i in range(s + 1)] for i in range(n + 1)]
dp0[0][0] = 1

for t in range(n):
    for r in range(s+1):
        if r >= a[t]:
            dp[t + 1][r] = dp[t][r] * 2 + dp[t][r - a[t]]
            dp0[t + 1][r] = dp0[t][r] + dp0[t][r - a[t]]
        else:
            dp[t + 1][r] = dp[t][r] * 2
            dp0[t + 1][r] = dp0[t][r]


b = dp[n]
c = b[(- (- s // 2)):(s + 1)]

if s % 2 == 1:
    conb = sum(b) - sum(c) * 3
else:

    conb = sum(b) - sum(c) * 3 + dp0[n][s//2] * 3

print(conb % M)

Submission status: Time Limit Exceeded

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


s = sum(a)

#dp[t][r]:0~t番目の整数を塗り分け、赤い整数の和がrであるような場合の数
dp = [[0 for i in range(s+1)] for i in range(n + 1)]
dp[0][0] = 1

for t in range(n):
    for r in range(s+1):
        if r >= a[t]:
            dp[t + 1][r] = dp[t][r] * 2 + dp[t][r - a[t]]
        else:
            dp[t + 1][r] = dp[t][r] * 2



b = dp[n]
c = b[(- (- s // 2)):(s + 1)]

if s % 2 == 1:
    conb = sum(b) - sum(c) * 3
else:
    dp0 = [[0 for i in range(s // 2 + 1)] for i in range(n + 1)]
    dp0[0][0] = 1
    for t in range(n):
        for r in range(s // 2 + 1):
            if r >= a[t]:
                dp0[t + 1][r] = dp0[t][r] + dp0[t][r - a[t]]
            else:
                dp0[t + 1][r] = dp0[t][r]
    conb = sum(b) - sum(c) * 3 + dp0[n][s//2] * 3

print(conb % M)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]

MOD = 998244353

s = sum(a)

# 三角形が存在しない組み合わせの数を求めるためのDP
dp0 = [0] * (s + 1)
dp0[0] = 1
for i in a:
    for idx in range(s, i-1, -1):
        dp0[idx] = (dp0[idx] + dp0[idx-i]*2) % MOD

# 足しなおす分のDP
dp1 = [0] * (s+1)
dp1[0] = 1
for i in a:
    for idx in range(s, i-1, -1):
        dp1[idx] = (dp1[idx] + dp1[idx-i]) % MOD

ans = pow(3, n, MOD)
# 解から三角形が存在しない通り数を引く
for l in range(0, s//2+1):
    ans = (ans - dp0[l]*3) % MOD
# 弾きすぎた分を足す
if s % 2 == 0:
    ans = (ans + dp1[s//2]*3) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    S = sum(A)
    a = A[0]
    # dp[i][j]: DP table for the number of one side length is j until i-th A[i].
    dp = [[0 for _ in range(S+1)] for _ in range(N)]
    dp[0][a] = 1
    dp[0][0] = 2

    # dp2[i][j]: DP table for the number of one side length is j and the other one is 0 until i-th A{i].
    dp2 = [[0 for _ in range(S+1)] for _ in range(N)]
    dp2[0][a] = 1
    dp2[0][0] = 1
    for i in range(1, N):
        a += A[i]
        for j in range(a+1):
            dp[i][j] = dp[i-1][j] * 2
            dp2[i][j] = dp2[i-1][j]

            if j >= A[i]:
                dp[i][j] += dp[i-1][j-A[i]]
                dp2[i][j] += dp2[i-1][j-A[i]]

            dp[i][j] %= MOD
            dp2[i][j] %= MOD

    ng = 0
    if S % 2 == 1:
        for i in range(S//2 + 1, S+1):
            ng += dp[N-1][i]

        ng = (ng * 3) % MOD

    else:
        for i in range(S//2, S+1):
            ng += dp[N-1][i]

        ng = (ng * 3 - dp2[N-1][S//2] * 3) % MOD

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


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

Submission status: Time Limit Exceeded

Solution code:
#!/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()

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    S = sum(A)
    dp = [[0 for _ in range(S+1)] for _ in range(N)]
    a = A[0]
    dp[0][a] = 1
    dp[0][0] = 2
    for i in range(1, N):
        a += A[i]
        for j in range(a+1):
            dp[i][j] = dp[i-1][j] * 2

            if j >= A[i]:
                dp[i][j] += dp[i-1][j-A[i]]

            dp[i][j] %= MOD

    dp2 = [[0 for _ in range(S+1)] for _ in range(N)]
    a = A[0]
    dp2[0][a] = 1
    dp2[0][0] = 1
    for i in range(1, N):
        a += A[i]
        for j in range(a+1):
            dp2[i][j] = dp2[i-1][j]

            if j >= A[i]:
                dp2[i][j] += dp2[i-1][j-A[i]]

            dp2[i][j] %= MOD

    ng = 0
    if S % 2 == 1:
        for i in range(S//2 + 1, S+1):
            ng += dp[N-1][i]

        ng = (ng * 3) % MOD

    else:
        for i in range(S//2, S+1):
            ng += dp[N-1][i]

        ng = (ng * 3 - dp2[N-1][S//2] * 3) % MOD

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

    
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
#!/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()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N = int(input())
a = sorted([int(input()) for _ in range(N)], reverse=True)

s = sum(a)
m = (s - 1) // 2
m1 = m + 1


@lru_cache(maxsize=None)
def func(n, r):
    if n == N - 1:
        if r + a[n] > m:
            return 1
        else:
            return 0
    elif r + a[n] > m:
        return 3 ** (N - n - 1) % 998244353 + 2 * func(n + 1, r) % 998244353
    else:
        return (func(n + 1, r + a[n]) + 2 * func(n + 1, r)) % 998244353


@lru_cache(maxsize=None)
def func1(n, r):
    if n == N - 1:
        if r + a[n] == m1:
            return 1
        else:
            return 0
    elif r + a[n] > m1:
        return func1(n + 1, r)
    elif r + a[n] == m1:
        return 1 + func1(n + 1, r)
    else:
        return func1(n + 1, r + a[n]) + func1(n + 1, r)


ans = 3 ** N % 998244353 - 3 * func(0, 0)
if s % 2 == 0:
    ans += 3 * func1(0, 0)

print(ans % 998244353)