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_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=dp_1[i-1][j]+dp_1[i-1][j-a_list[i]]
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=(Sum+dp[n][i]*3)%mod
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=dp_1[i-1][j]+dp_1[i-1][j-a_list[i]]
        else:
            dp[i][j]=dp[i-1][j]*2
            dp_1[i][j]=dp_1[i-1][j]
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=Sum+dp[n][i]*3
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a_list=[0]
for i in range(n):
    a_list.append(int(input()))
S=sum(a_list)
dp=[]
dp_1=[]
mod=998244353
for i in range(n+1):
    sub_list=[0]*(S+1)
    dp.append(sub_list)
    sub_list=[0]*(S+1)
    dp_1.append(sub_list)
dp[0][0]=1
dp_1[0][0]=1
for i in range(1,n+1):
    for j in range(S+1):
        if j>=a_list[i]:
            dp[i][j]=(dp[i-1][j]*2+dp[i-1][j-a_list[i]])%mod
            dp_1[i][j]=dp_1[i-1][j]+dp_1[i-1][j-a_list[i]]
        else:
            dp[i][j]=dp[i-1][j]*2%mod
            dp_1[i][j]=dp_1[i-1][j]
Sum=0
for i in range(S+1):
    if i>S/2:
        Sum=Sum+dp[n][i]*3
    elif i==S/2:
        Sum=Sum+dp[n][i]*3-dp_1[n][i]*3
ans=(pow(3,n,mod)-Sum)%mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
for _ in range(n):
  l.append(int(input()))
l.sort(reverse=True)
border = (sum(l) + 1) // 2

numDict = dict()
numDict[(0,0,0)] = 1
for i in l:
  tempDict = dict()
  for k, v in numDict.items():
    if k[0] + i < border:
      if (k[0] + i, k[1], k[2]) in tempDict:
        tempDict[(k[0] + i, k[1], k[2])] = (tempDict[(k[0] + i, k[1], k[2])] + v) % 998244353
      else:
        tempDict[(k[0] + i, k[1], k[2])] = v
    if k[1] + i < border:
      if (k[0], k[1] + i, k[2]) in tempDict:
        tempDict[(k[0], k[1] + i, k[2])] = (tempDict[(k[0], k[1] + i, k[2])] + v)  % 998244353
      else:
        tempDict[(k[0], k[1] + i, k[2])] = v
    if k[2] + i < border:
      if (k[0], k[1], k[2] + i) in tempDict:
        tempDict[(k[0], k[1], k[2] + i)] = (tempDict[(k[0], k[1], k[2] + i)] + v)  % 998244353
      else:
        tempDict[(k[0], k[1], k[2] + i)] = v
  numDict = tempDict

print(sum(numDict.values()) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
l = []
for _ in range(n):
  l.append(int(input()))
l.sort(reverse=True)
border = (sum(l) + 1) // 2

numDict = dict()
numDict[(0,0,0)] = 1
for i in l:
  tempDict = dict()
  for k, v in numDict.items():
    if k[0] + i < border:
      if (k[0] + i, k[1], k[2]) in tempDict:
        tempDict[(k[0] + i, k[1], k[2])] = (tempDict[(k[0] + i, k[1], k[2])] + v % 998244353) % 998244353
      else:
        tempDict[(k[0] + i, k[1], k[2])] = v % 998244353
    if k[1] + i < border:
      if (k[0], k[1] + i, k[2]) in tempDict:
        tempDict[(k[0], k[1] + i, k[2])] = (tempDict[(k[0], k[1] + i, k[2])] + v % 998244353)  % 998244353
      else:
        tempDict[(k[0], k[1] + i, k[2])] = v  % 998244353
    if k[2] + i < border:
      if (k[0], k[1], k[2] + i) in tempDict:
        tempDict[(k[0], k[1], k[2] + i)] = (tempDict[(k[0], k[1], k[2] + i)] + v % 998244353)  % 998244353
      else:
        tempDict[(k[0], k[1], k[2] + i)] = v  % 998244353
  numDict = tempDict

print(sum(numDict.values()) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n = int(input())
a_list = []

for i in range(n):
    a_list.append(int(input()))
sum_s = sum(a_list)

half = sum_s // 2
if sum_s % 2 != 0:
    half += 1

# a が sum_s / 2 以上
a_dp = [[0 for j in range(sum_s+1)] for i in range(n)]
a_dp[0][a_list[0]] = 1
a_dp[0][0] = 2

for i in range(1, n):

    for j in range(sum_s+1):
        # aに塗った場合
        if j + a_list[i] <= sum_s:
            a_dp[i][j+a_list[i]] += a_dp[i-1][j]
        # aに塗らなかった場合
        a_dp[i][j] += a_dp[i - 1][j] * 2

sum_a = sum(a_dp[n-1][half:])

# aとbが sum_s/2 [pos][total_a][total_r]
b_dp = [[[0 for k in range(sum_s+1)] for j in range(sum_s+1)] for i in range(n)]
b_dp[0][a_list[0]][0] = 1
b_dp[0][0][a_list[0]] = 1
b_dp[0][0][0] = 1

for i in range(1, n):
    # aに塗った場合
    for j in range(sum_s+1):
        for k in range(sum_s+1):
            # a塗った場合
            if j + a_list[i] <= sum_s:
                b_dp[i][j+a_list[i]][k] += b_dp[i-1][j][k]
            # rに塗った場合
            if k + a_list[i] <= sum_s:
                b_dp[i][j][k + a_list[i]] += b_dp[i - 1][j][k]
            # gに塗った場合
            b_dp[i][j][k] += b_dp[i-1][j][k]

sum_b = b_dp[n-1][half][half]
ans = pow(3, n) - (3*sum_a) + (3*sum_b)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
import queue
import re
import math
import functools
import numpy as np

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = np.zeros((N+1, SUM+1), dtype=np.int)
    dp3 = np.zeros((N+1, SUM+1), dtype=np.int)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=(2*dp3[n][s])%DIV
            if s>=a:
                dp1[n+1][s]= (dp1[n+1][s]+ dp1[n][s-a])%DIV
                dp3[n+1][s]= (dp3[n+1][s]+ dp3[n][s-a])%DIV
    S3 = (sum(dp3[N][(SUM+1)//2:])*3)%DIV
    S1 = (dp1[N][(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = 1
for _ in range(N):
    ALL = (ALL*3)%DIV

def main():
    dp1 = make2d_arr(N+1,SUM+1,0)
    dp3 = make2d_arr(N+1,SUM+1,0)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=(2*dp3[n][s])%DIV
            if s>=a:
                dp1[n+1][s]= (dp1[n+1][s]+ dp1[n][s-a])%DIV
                dp3[n+1][s]= (dp3[n+1][s]+ dp3[n][s-a])%DIV
    S3 = (sum(dp3[N][(SUM+1)//2:])*3)%DIV
    S1 = (dp1[N][(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = (3**N)%DIV

def main():
    dp1 = make2d_arr(N+1,SUM+1,0)
    dp3 = make2d_arr(N+1,SUM+1,0)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=(2*dp3[n][s])%DIV
            if s>=a:
                dp1[n+1][s]= (dp1[n+1][s]+ dp1[n][s-a])%DIV
                dp3[n+1][s]= (dp3[n+1][s]+ dp3[n][s-a])%DIV
    S3 = (sum(dp3[N][(SUM+1)//2:])*3)%DIV
    S1 = (dp1[N][(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush,heappop
import queue
import re
import math
import functools


def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def make1d_arr(n,val=INF):
    return [val for i in range(n)]

def make2d_arr(h,w,val =INF):
    return [[val for i in range(w)]for i in range(h)]

def gcd (a,b):
    if(b==0):
        return a
    return gcd(b,a%b)


N = int_raw()
As =[]
for _ in range(N):
    As.append(int_raw())
SUM = sum(As)

DIV = 998244353

ALL = (3**N)

def main():
    dp1 = make2d_arr(N+1,SUM+1,0)
    dp3 = make2d_arr(N+1,SUM+1,0)
    dp1[0][0]=1
    dp3[0][0]=1
    
    for n in range(N):
        a = As[n]
        for s in range(SUM+1):
            dp1[n+1][s]=dp1[n][s]
            dp3[n+1][s]=2*dp3[n][s]
            if s>=a:
                dp1[n+1][s]+=dp1[n][s-a]
                dp3[n+1][s]+=dp3[n][s-a]
    S3 = sum(dp3[N][(SUM+1)//2:])*3
    S1 = dp1[N][(SUM)//2]*3 if SUM%2==0 else 0
    return (ALL - S3 + S1) % DIV

print(main())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
numbers = [int(input()) for _ in range(N)]

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = [[0 for _ in range(S + 1)] for _ in range(N)]
count3[0][0] = 2
count3[0][numbers[0]] = 1
count2 = [[0 for _ in range(S + 1)] for _ in range(N)]
count2[0][0] = 1
count2[0][numbers[0]] = 1

for i in range(1, N):
  for j in range(S + 1):
    if (count3[i - 1][j] > 0):
      count3[i][j + numbers[i]] += count3[i - 1][j]
      count3[i][j + numbers[i]] %= M
      count3[i][j] += 2 * count3[i - 1][j]
      count3[i][j] %= M
      count2[i][j + numbers[i]] += count2[i - 1][j]
      count2[i][j + numbers[i]] %= M
      count2[i][j] += count2[i - 1][j]
      count2[i][j] %= M

count_invalid = 0
for i in range(S):
  if (i > S / 2):
    count_invalid += count3[N - 1][i] - 2 * count2[N - 1][i]
    count_invalid %= M
if (S % 2 == 0):
  count_invalid += count3[N - 1][S // 2] - 2 * count2[N - 1][S // 2]
  count_invalid %= M

print((count_all - 3 * count_invalid) % M)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
numbers = [int(input()) for _ in range(N)]

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = [[0 for _ in range(S + 1)] for _ in range(N)]
count3[0][0] = 2
count3[0][numbers[0]] = 1
count2 = [[0 for _ in range(S + 1)] for _ in range(N)]
count2[0][0] = 1
count2[0][numbers[0]] = 1

for i in range(1, N):
  for j in range(S + 1):
    if (count3[i - 1][j] > 0):
      count3[i][j + numbers[i]] += count3[i - 1][j]
      count3[i][j] += 2 * count3[i - 1][j]
      count2[i][j + numbers[i]] += count2[i - 1][j]
      count2[i][j] += count2[i - 1][j]

count_invalid = 0
for i in range(S):
  if (i > S / 2):
    count_invalid += count3[N - 1][i] - 2 * count2[N - 1][i]
if (S % 2 == 0):
  count_invalid += count3[N - 1][S // 2] - 2 * count2[N - 1][S // 2]

print((count_all - 3 * count_invalid) % M)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
numbers = [int(input()) for _ in range(N)]

M = 998244353
count_all = (3 ** N - 3 * (2 ** N - 2) - 3) % M

S = sum(numbers)
count3 = [0 for _ in range(S + 1)]
count3[0] = 2
count3[numbers[0]] = 1
count2 = [0 for _ in range(S + 1)]
count2[0] = 1
count2[numbers[0]] = 1

for i in range(1, N):
  count3_next = [0 for _ in range(S + 1)]
  count2_next = [0 for _ in range(S + 1)]
  for j in range(S + 1):
    if (count3[j] > 0):
      count3_next[j + numbers[i]] += count3[j]
      count3_next[j] += 2 * count3[j]
      count2_next[j + numbers[i]] += count2[j]
      count2_next[j] += count2[j]
  count3 = count3_next
  count2 = count2_next

count_invalid = 0
for i in range(S):
  if (i > S / 2):
    count_invalid += count3[i] - 2 * count2[i]
if (S % 2 == 0):
  count_invalid += count3[S // 2] - 2 * count2[S // 2]

print((count_all - 3 * count_invalid) % M)

Submission status: Time Limit Exceeded

Solution code:
import math

n = int(input())
arr = sorted([ int(input()) for _ in range(n) ], reverse = True )


sum = 0
for x in arr:
    sum += x
half=sum/2

def over_red(pos, r):

    if pos == n:
        if r >= half:
            return 1
        else:
            return 0

    if memo[pos][r] != -1:
        return memo[pos][r]
    
    val = over_red(pos+1, r) * 2 + over_red(pos+1, r + arr[pos])
    memo[pos][r] = val

    return val

def just_half(pos, r):
    if pos == n:
        if r == half:
            return 1
        else:
            return 0
    
    if r > half:
        return 0

    if memo[pos][r] != -1:
        return memo[pos][r]
    
    val = just_half(pos+1, r) + just_half(pos+1, r + arr[pos])
    memo[pos][r] = val
    return val

# 全体 - (Rが超過)*3 + (RとBがちょうど半分)*3
all_patterns = 3 ** n
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
over_red_patterns = over_red(0,0)*3
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
just_half_patterns = just_half(0,0) * 3
print( (all_patterns - over_red_patterns + just_half_patterns)  % 998244353 )

Submission status: Time Limit Exceeded

Solution code:
import math

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


sum = 0
for x in arr:
    sum += x
half=sum/2

def over_red(pos, r):

    if pos == n:
        if r >= half:
            return 1
        else:
            return 0

    if memo[pos][r] != -1:
        return memo[pos][r]
    
    val = over_red(pos+1, r) * 2 + over_red(pos+1, r + arr[pos])
    memo[pos][r] = val

    return val

def just_half(pos, r):
    if pos == n:
        if r == half:
            return 1
        else:
            return 0
    
    if r > half:
        return 0

    if memo[pos][r] != -1:
        return memo[pos][r]
    
    val = just_half(pos+1, r) + just_half(pos+1, r + arr[pos])
    memo[pos][r] = val
    return val

# 全体 - (Rが超過)*3 + (RとBがちょうど半分)*3
all_patterns = 3 ** n
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
over_red_patterns = over_red(0,0)*3
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
just_half_patterns = just_half(0,0) * 3
print( (all_patterns - over_red_patterns + just_half_patterns)  % 998244353 )

Submission status: Time Limit Exceeded

Solution code:
import math

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


sum = 0
for x in arr:
    sum += x
half=sum/2

def over_red(pos, r):

    if pos == n:
        if r >= half:
            return 1
        else:
            return 0

    if memo[pos][r] != -1:
        return memo[pos][r]
    
    val = over_red(pos+1, r) * 2 + over_red(pos+1, r + arr[pos])
    memo[pos][r] = val

    return val

def just_half(pos, r):
    if pos == n:
        if r == half:
            return 1
        else:
            return 0

    if memo[pos][r] != -1:
        return memo[pos][r]
    
    val = just_half(pos+1, r) + just_half(pos+1, r + arr[pos])
    memo[pos][r] = val
    return val

# 全体 - (Rが超過)*3 + (RとBがちょうど半分)*3
all_patterns = 3 ** n
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
over_red_patterns = over_red(0,0)*3
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
just_half_patterns = just_half(0,0) * 3
print( (all_patterns - over_red_patterns + just_half_patterns)  % 998244353 )

Submission status: Time Limit Exceeded

Solution code:
import math

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


sum = 0
for x in arr:
    sum += x
half=sum/2

def over_red(pos, r):

    if pos == n:
        if r >= half:
            return 1
        else:
            return 0

    if memo[pos][r] != -1:
        return memo[pos][r]
    
    val = over_red(pos+1, r) * 2 + over_red(pos+1, r + arr[pos])
    memo[pos][r] = val

    return val

def just_half(pos, r):
    if pos == n:
        if r == half:
            return 1
        else:
            return 0

    return just_half(pos+1, r) + just_half(pos+1, r + arr[pos])

# 全体 - (Rが超過)*3 + (RとBがちょうど半分)*3
all_patterns = 3 ** n
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
over_red_patterns = over_red(0,0)*3
memo=[ [ -1 for _ in range(sum)] for _ in range(n)]
just_half_patterns = just_half(0,0) * 3
print( (all_patterns - over_red_patterns + just_half_patterns)  % 998244353 )

Submission status: Time Limit Exceeded

Solution code:
m = 998244353

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

'''
def mod(n,m):
    while not (0 <= n < m):
        if n > 0:
            n -= m
        else:
            n += m
    return n
'''

s = sum(l)
dp3 = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp2 = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp3[0][0] = 1
dp2[0][0] = 1

for i,x in enumerate(l):
    for j,y in enumerate(dp3[i]):
        if y != 0:
            dp3[i+1][j] = (dp3[i+1][j] + y*2) % m
            dp3[i+1][j+x] = (dp3[i+1][j+x] + y) % m
    for j,y in enumerate(dp2[i]):
        if y != 0:
            dp2[i+1][j] += y
            dp2[i+1][j] %= m
            dp2[i+1][j+x] += y
            dp2[i+1][j+x] %= m

a = 1
for i in range(n):
    a = a*3 % m

if s%2 == 0:
    ans = a - 3 * sum(dp3[n][s//2:])
    if dp3[n][s//2] > 0:
        ans += dp2[n][s//2] * 3
else:
    ans = a - 3 * sum(dp3[n][s//2+1:])

print(ans % m)

Submission status: Time Limit Exceeded

Solution code:
m = 998244353

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

def mod(n,m):
    while not (0 <= n < m):
        if n > 0:
            n -= m
        else:
            n += m
    return n

s = sum(l)
dp3 = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp2 = [[0 for _ in range(s+1)] for _ in range(n+1)]
dp3[0][0] = 1
dp2[0][0] = 1

for i,x in enumerate(l):
    for j,y in enumerate(dp3[i]):
        if y != 0:
            dp3[i+1][j] += y*2
            dp3[i+1][j+x] += y
    for j,y in enumerate(dp2[i]):
        if y != 0:
            dp2[i+1][j] += y
            dp2[i+1][j+x] += y

a = 1
for i in range(n):
    a = mod(a*3, m)

if s%2 == 0:
    ans = a - 3 * sum(dp3[n][s//2:])
    if dp3[n][s//2] > 0:
        ans += dp2[n][s//2] * 3
else:
    ans = a - 3 * sum(dp3[n][s//2+1:])

print(mod(ans,m))

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

S = sum(A)
memo0 = [0] * (S+1)
memo1 = [0] * (S+1)
memo0[0] = 1
memo1[0] = 1


# なんで大きい方から小さくしていくのか
def dp0():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo0[s] = (memo0[s] + memo0[s-A[i]]*2) % MOD


# 辺を2グループにわけるDP
def dp1():
    for i in range(n):
        for s in range(S, A[i]-1, -1):
            memo1[s] = (memo1[s] + memo1[s-A[i]]) % MOD


dp0()
dp1()
# 実装方法を変える
ans = pow(3, n, MOD)
# 解から三角形が存在しない通りを引く
for l in range(0, S//2+1):
    ans = (ans - memo0[l]*3) % MOD
# 引きすぎた分を引く
if S % 2 == 0:
    ans = (ans + memo1[S//2]*3) % MOD


print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(input()) for _ in range(N)]
s = sum(a)
den = 998244353

dp1 = [[0]*(s+1) for _ in range(N)]  # R >= S/2
dp1[0][0] = 2
dp1[0][a[0]] = 1
if s % 2 == 0:
    dp2 = [[0]*(s+1) for _ in range(N)]  # R = G = S/2
    dp2[0][0] = 1
    dp2[0][a[0]] = 1

for t in range(1, N):
    for r in range(s+1):
        if r >= a[t]:
            dp1[t][r] = (2*dp1[t-1][r] + dp1[t-1][r-a[t]]) % den
            if s % 2 == 0:
                dp2[t][r] = (dp2[t-1][r] + dp2[t-1][r-a[t]]) % den
        else:
            dp1[t][r] = (2*dp1[t-1][r]) % den
            if s % 2 == 0:
                dp2[t][r] = (dp2[t-1][r]) % den

whole = 1
for i in range(N):
    whole *= 3
    whole %= den

single = 0
for i in range((s+1)//2, s+1):
    single += dp1[N-1][i]
    single %= den

if s % 2 == 0:
    double = dp2[N-1][s//2]
else:
    double = 0

out = (whole - 3*single + 3*double) % den
print(out)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

# N = 4
# a = np.array([1, 1, 1, 2]).astype(np.int64)
S = a.sum()

# 最初のt個の整数を塗り分け, Rの整数の和がrであるような場合の数
DP_A = np.zeros((N+1, S+1), dtype=np.int64)
# 最初のt個の整数を塗り分け, Rの整数の和がrで, Bの和が0であるような場合の数
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):
    for r in range(S + 1):
        # t + 1番目の整数をRにしない -> G or Bにする
        DP_A[t+1, r] = DP_A[t, r] * 2 % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_A[t+1, r] += DP_A[t, r - a[t]] % m
        # t+1 番目の整数をRにしない -> Gを加える
        DP_B[t+1, r] = DP_B[t, r] % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_B[t+1, r] += DP_B[t, r - 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)

Submission status: Time Limit Exceeded

Solution code:
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[i][j] represents sum of red is j at i position
	dp = [[0 for _ in range(summation+1)] for _ in range(N)]
	dp[0][0] = 2 # green or blue
	dp[0][A[0]] = 1 # red

	for i in range(1, N):
		for j in range(len(dp[i])):
			dp[i][j] += dp[i-1][j] * 2 % MOD # don't use A[i] for red, i.e. use green or blue
			dp[i][j] += dp[i-1][j-A[i]] % MOD if 0 <= j - A[i] <= len(dp[i]) else 0 # use i red

	# total
	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:
		# case r = g = S/2
		dp  =[[0 for _ in range(summation//2+1)] for _ in range(N)]
		dp[0][0] = 1 # only blue
		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()

Submission status: Time Limit Exceeded

Solution code:
def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    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[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

    # init
    dp[0][A[0]] = 1
    dp[0][0] = 2  # 他の色のうちどちらに入れるかで2通り

    # init2
    dp2 = [[0] * (sum_A+1) for i in range(N)]  # ある二色でsum_Aを等分するパターンを数える
    dp2[0][A[0]] = 1
    dp2[0][0] = 1  # 今度は片方に集中したパターン

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            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
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    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()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math

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

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]
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]
  bad_rg = dp2[N][0]
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)
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]
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]
  bad_rg = dp2[N][0]
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)]
### 三角形が成立しない場合を数える
alist.sort(reverse=True) #大きい方からチェックするとS/2に早く到達しやすい
MOD = 998244353
asum = [0]
for i in range(N):
    asum += [asum[-1] + alist[i]]
S = asum[-1]
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
    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:
import math

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

S = sum(A)
maxA = max(A)
dp = [[0 for i in range(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]
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0 for i in range(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]
  bad_rg = dp2[N][0]
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)
maxA = max(A)
dp = [[0 for i in range(S+1+maxA-math.ceil(S/2))] for j in range(N+1)]
dp[0][S+1-math.ceil(S/2)-1]=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]
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0 for i in range(S+1+maxA-math.ceil(S/2))] for j in range(N+1)]
  dp2[0][S+1-math.ceil(S/2)-1]=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]
  bad_rg = dp2[N][0]
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)
maxA = max(A)
dp = [[0 for i in range(S+1+maxA)] 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):
    dp[i][j] = dp[i-1][j+A[i-1]]*2 + dp[i-1][j]
bad_r = sum(dp[N])

if S%2 == 0:
  dp2 = [[0 for i in range(S+1+maxA)] 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):
      dp2[i][j] = dp2[i-1][j+A[i-1]] + 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)