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: Wrong Answer

Solution code:
from sys import stdin
# import math
import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]

N = int(stdin.readline().rstrip().split()[0])
A=[]
for i in range(N):
  A.append(int(stdin.readline().rstrip().split()[0]))

MOD = 998244353
A.sort()
cumsum = np.cumsum(A)
# A=A[::-1]

def tri(RGB):
  R,G,B=RGB
  arr = [R,G,B]
  arr.sort()
  if arr[2]<arr[0]+arr[1]:
    return 1
  else:
    return 0

DP_memo = {}
DP_memo[0] = {}
def DP(RGB,n):
  R,G,B = RGB
  arr = [R,G,B]
  arr.sort()
  RGB = tuple(arr)
  if n in DP_memo:
    if RGB in DP_memo[n]:
      return DP_memo[n][RGB]
  else:
    DP_memo[n] = {}

  if n==N:
    return tri(RGB)
  if B-(R+G+cumsum[N-n-1])>=0:
    if n+1 in DP_memo:
      DP_memo[n][RGB]=0
    else:
      DP_memo[n]={}
      DP_memo[n][RGB]=0
    return 0
  
  ret = 0
  ret += DP((R+A[n],G,B),n+1)
  ret += DP((R,G+A[n],B),n+1)
  ret += DP((R,G,B+A[n]),n+1)
  if n+1 in DP_memo:
    DP_memo[n][RGB]=ret
  else:
    DP_memo[n]={}
    DP_memo[n][RGB]=ret
  return ret
  
  

ans=DP((0,0,0), 0)
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
n=int(input())
mod=998244353
A=[int(input()) for i in range(n)]
def N(i,r,g,b):
  count=0
  if i==0:
    if r>=A[0]:
      count+=1
    if g>=A[0]:
      count+=1
    if b>=A[0]:
      count+=1
    return count
  else:
    return N(i-1,r-A[i],g,b)+N(i-1,r,g-A[i],b)+N(i-1,r,g,b-A[i])
s=sum(A)
print(N(n-1,(s-1)//2,(s-1)//2,(s-1)//2)%mod)

Submission status: Wrong Answer

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

mod = 998244353
memo = {}


def merge_count(ls):
    if len(ls) == 3:
        if abs(ls[1] - ls[2]) < ls[0] < ls[1] + ls[2] and ls[0] > 0 and ls[1] > 0 and ls[2] > 0:
            return 1
        else:
            return 0

    count = 0
    for i in range(len(ls) - 1):
        for j in range(1 + i, len(ls)):
            merged = sorted(ls[:i] + ls[i+1:j] + ls[j+1:] + [ls[i] + ls[j]])
            merged_tuple = tuple(merged)
            if merged_tuple in memo:
                count += memo[merged_tuple]
            else:
                c = merge_count(merged)
                count += c
                memo[merged_tuple] = c
    return count % mod


print((merge_count(sorted(a)) * 6) % mod)

Submission status: Wrong Answer

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
print(l)
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 % 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
      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
      else:
        tempDict[(k[0], k[1], k[2] + i)] = v  % 998244353
  numDict = tempDict

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

Submission status: Wrong Answer

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
print(l)
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
      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
      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
      else:
        tempDict[(k[0], k[1], k[2] + i)] = v
  numDict = tempDict

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

Submission status: Wrong Answer

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

n = readInt()
aa = []
for i in range(n):
    aa.append(readInt())

#memo = {}


#def dfs(a, b, c, i):
#    if i == len(aa):
#        return 1 if c < a + b else 0
##    if (a, b, c, i) in memo:
##        return memo[(a, b, c, i)]
#
#    ret = 0
#    v0 = sorted([a + aa[i], b, c])
#    ret = (ret + dfs(*v0, i + 1)) % 998244353
#
#    v1 = sorted([a, b + aa[i], c])
#    ret = (ret + dfs(*v1, i + 1)) % 998244353
#
#    v2 = sorted([a, b, c + aa[i]])
#    ret = (ret + dfs(*v2, i + 1)) % 998244353
#
##    memo[(a, b, c, i)] = ret
#    return ret
#
#
#ret = dfs(0, 0, 0, 0)
#print(ret)
print(100)

Submission status: Wrong Answer

Solution code:
N = int(input())
a = [int(input()) for i in range(N)]

state = {(0,0,0):1}
for s in a:
    new_state = {}
    for x, j in state.items():
        for v in ((1,0,0), (0,1,0), (0,0,1)):
            n = tuple(sorted((s*v[0]+x[0], s*v[1]+x[1], s*v[2]+x[2])))
            if not n in new_state:
                new_state[n] = j
            else:
                new_state[n] += j
    new_state, state = state, new_state

ans = 0
for x, j in state.items():
    print(x, j)
    if x[0]!=0 and x[1]!=0 and x[2]!=0\
       and x[0]<x[1]+x[2]\
       and x[1]<x[0]+x[2]\
       and x[2]<x[0]+x[1]:       
        ans = (ans+j)%998244353

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

for ai in a:
    acc.append(acc[-1]+ai)

S = acc[-1]
MOD = 998244353
dp1 = [[0]*(S+1) for _ in range(2)]
dp1[0][0] = 1

for i in range(N):
    for j in range(S+1):
        dp1[(i+1)%2][j] = 0
        
    for j in range(acc[i]+1):
        dp1[(i+1)%2][j] += 2*dp1[i%2][j]
        dp1[(i+1)%2][j] %= MOD
        dp1[(i+1)%2][j+a[i]] += dp1[i%2][j]
        dp1[(i+1)%2][j+a[i]] %= MOD
            
ans = (pow(3, N, MOD)-3*sum(dp1[N%2][(S+1)//2:])%MOD)%MOD

if S%2==0:
    dp2 = [[0]*(S+1) for _ in range(2)]
    dp2[0][0] = 1
    
    for i in range(N):
        for j in range(S+1):
            dp2[(i+1)%2][j] = 0
            
        for j in range(acc[i]+1):
            dp2[(i+1)%2][j] += dp2[i%2][j]
            dp2[(i+1)%2][j] %= MOD
            dp2[(i+1)%2][j+a[i]] += dp2[i%2][j]
            dp2[(i+1)%2][j+a[i]] %= MOD
                
    ans += 3*dp2[N%2][S//2]
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
a = [int(input()) for _ in range(N)]
MOD = 998244353
dp1 = [[0]*(N*300+1) for _ in range(2)]
dp1[0][0] = 1

for i in range(N):
    for j in range(N*300+1):
        dp1[(i+1)%2][j] = 0
        
    for j in range(N*300+1):
        dp1[(i+1)%2][j] += 2*dp1[i%2][j]
        dp1[(i+1)%2][j] %= MOD
        
        if j+a[i]<=N*300:
            dp1[(i+1)%2][j+a[i]] += dp1[i%2][j]
            dp1[(i+1)%2][j+a[i]] %= MOD
            
S = sum(a)
ans = (pow(3, N, MOD)-3*sum(dp1[N%2][(S+1)//2:])%MOD)%MOD

if S%2==0:
    dp2 = [[0]*(N*300+1) for _ in range(2)]
    dp2[0][0] = 1
    
    for i in range(N):
        for j in range(N*300+1):
            dp2[(i+1)%2][j] = 0
            
        for j in range(N*300+1):
            dp2[(i+1)%2][j] += dp2[i%2][j]
            dp2[(i+1)%2][j] %= MOD
        
            if j+a[i]<=N*300:
                dp2[(i+1)%2][j+a[i]] += dp2[i%2][j]
                dp2[(i+1)%2][j+a[i]] %= MOD
                
    ans += 3*dp2[N%2][S//2]
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = sorted([int(input()) for _ in [0]*n])
    dp = [1]
    DP = [1]
    s = 1
    mod = 998244353
    for i in a:
        dp2 = dp+([0]*i)
        DP2 = DP+([0]*i)
        for j in range(s):
            dp2[i+j] = (dp2[i+j]+2*dp[j]) % mod
            DP2[i+j] = (DP2[i+j]+DP[j]) % mod
        dp = dp2
        DP = DP2
        s += i
    ALL = sum(dp)
    A = sum(dp[(s-1)//2+1:])
    if s % 2 == 1:
        B = DP[s//2]
    else:
        B = 0
    print((3*A-2*ALL+3*B) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
S=sum(A)

dp=[0 for j in range(S+1)]
sub=[0 for j in range(S+1)]
dp[0]=pow(2,N,mod)
dp[A[0]]=pow(2,N-1,mod)
sub[0]=1
sub[A[0]]=1

for i in range(1,N):
    for j in range(S,-1,-1):
        dp[j]=(dp[j]+pow(2,mod-2,mod)*(j>=A[i])*dp[j-A[i]])%mod
        sub[j]=(sub[j]+(j>=A[i])*sub[j-A[i]])%mod

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[i]
        ans%=mod
    ans+=3*sub[S//2]
    ans%=mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
S=sum(A)

dp=[[0 for j in range(S+1)] for i in range(N)]
sub=[[0 for j in range(S+1)] for i in range(N)]
dp[0][0]=pow(2,N,mod)
dp[0][A[0]]=pow(2,N-1,mod)
sub[0][0]=1
sub[0][A[0]]=1

for i in range(1,N):
    for j in range(S+1):
        dp[i][j]=(dp[i-1][j]+pow(2,mod-2,mod)*(j>=A[i])*dp[i-1][j-A[i]])%mod
        sub[i][j]=(sub[i-1][j]+(j>=A[i])*sub[i-1][j-A[i]])%mod

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    ans+=3*sub[N-1][S//2]
    ans%=mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
S=sum(A)

dp=[[0 for j in range(S+1)] for i in range(N)]
dp[0][0]=pow(2,N,mod)
dp[0][A[0]]=pow(2,N-1,mod)

for i in range(1,N):
    for j in range(S+1):
        dp[i][j]=(dp[i-1][j]+pow(2,mod-2,mod)*(j>=A[i])*dp[i-1][j-A[i]])%mod

if S%2==1:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    print(ans)
else:
    ans=pow(3,N,mod)
    for i in range((S+1)//2,S+1):
        ans-=3*dp[N-1][i]
        ans%=mod
    dp=[[0 for j in range(S+1)] for i in range(N)]
    dp[0][0]=1
    dp[0][A[0]]=1

    for i in range(1,N):
        for j in range(S+1):
            dp[i][j]=(dp[i-1][j]+(j>=A[i])*dp[i-1][j-A[i]])%mod
    ans+=3*dp[N-1][S//2]
    ans%=mod
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
Writer:SPD_9X2
https://atcoder.jp/contests/tenka1-2019-beginner/tasks/tenka1_2019_d

愚直全探索は 0(3**N)
O(N**3)位までは計算量を落とさないといけない

ありうる辺の長さ全列挙→むりぽ
短い2辺の和 < 長い辺の和　なら構成不可能
構成不可能分配の方を数える？

少なくとも各辺に1本分配する場合、
構成不可能な場合の最長辺の長さは必ず総延長の半分以上となる
総延長の半分以上となる取り方の数を数えて引けばよい？

長さとしてありうるのは 300**2 までしかありえないので、
dp推移をO(1)でやれば解けそう

具体的なdp推移を考えてみる
最長辺を赤と決めてあげてよい？

全部赤に割り振って減らしていく
→Nこの中からいくつか取って、半分以上の長さにする方法を網羅できる

調整
→最長3色分をやると、2色に半分ずつ行った時をダブルカウントしてるので処理する

解けた！！ O(sum(a)*N)

→解けてねぇ！！！！！！！
1本の辺の作り方を数えても結局残りの辺の数によって分配が依存してしまう…

N本からA本選んで長さの半分を超える方法がいくつあるか数えればよい
そうすれば残りの分配をO(1)でできる

=======答えを見た========

最初の方針で行けるやん…？
DP[r] = 赤の数がrであるような「塗り分けの個数」

"""

import math
mod = 998244353
N = int(input())

a = []

for i in range(N):

    A = int(input())
    a.append(A)

asum = sum(a)
lis = [0] * ( asum + 1)
lis[0] = 1

for i in range(N):

    nlis = [0] * (asum+1)
    for j in range(asum+1):

        nlis[j] += lis[j] * 2
        if j+a[i] <= asum:
            nlis[j+a[i]] += lis[j]

    lis = nlis

#print (lis)
ans = pow(3,N,mod)
#print (ans)

if asum % 2 == 1:
    for i in range( asum//2+1 , asum+1):
        ans -= lis[i] * 3
        ans %= mod

    print (ans)

else:
    for i in range( asum//2 , asum+1):
        ans -= lis[i] * 3
        ans %= mod

    #ダブルカウントを引く→数個選んで半分取る方法の個数を数える→//2
    #その個数*3*2が2回カウントされてるので足す

    lis2 = [0] * (asum+1)
    lis2[0] = 1

    for i in range(N):
        for j in range(asum-a[i],-1,-1):
            lis2[j+a[i]] += lis2[j]
            lis2[j+a[i]] %= mod

    ans += lis2[asum//2] * 3
    print (ans % mod)
        

#WA解
"""
import math
mod = 998244353
N = int(input())

a = []

for i in range(N):

    A = int(input())
    a.append(A)

asum = sum(a)
lis = [0] * ( asum + 1)
lis[-1] = 1

for i in range(N):

    for j in range(len(lis)):

        if j - a[i] >= 0:
            lis[j-a[i]] += lis[j]
            lis[j-a[i]] %= mod

print (lis)
ans = pow(3,N,mod)
print (ans)

if asum % 2 == 1:
    for i in range( asum//2 , asum+1):
        ans -= lis[i] * 6
        ans %= mod

    print (ans)

"""

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353

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

S = sum(A)

dp1 = [[0] * (S+1) for _ in range(N+1)]
dp1[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp1[i+1][r+A[i]] += dp1[i][r]
            dp1[i+1][r+A[i]] %= mod
        dp1[i+1][r] += 2 * dp1[i][r]
        dp1[i+1][r] %= mod

dp2 = [[0] * (S+1) for _ in range(N+1)]
dp2[0][0] = 1
for i in range(N):
    for r in range(S+1):
        if r + A[i] < S+1:
            dp2[i+1][r+A[i]] += dp2[i][r]
            dp2[i+1][r+A[i]] %= mod
        dp2[i+1][r] += dp2[i][r]
        dp2[i+1][r] %= mod

res1 = sum(dp1[N][r] for r in range(-(-S//2), S+1))
res2 = dp2[N][S//2] if S % 2 == 0 else 0

ans = pow(3, N, mod) - (3*res1 - 3*res2)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def I():
        return int(sys.stdin.readline())

    def LI():
        return list(map(int, sys.stdin.readline().split()))

    mod = 998244353
    ans = []

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

    sumA = sum(a)

    dp = [[0] * (sumA + 301) for _ in range(N)]
    start = (sumA + 1) // 2

    dp[0][0] = 2
    dp[0][a[0]] = 1

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

    # print(dp)
    out = sum(dp[N - 1][start:])
    ans = (3 ** N - out * 3) % mod
    # print(ans)

    if sumA % 2 == 0:
        dp = [[0] * (sumA + 301) for _ in range(N)]
        dp[0][0] = 1
        dp[0][a[0]] = 1
        for i in range(N - 1):
            for j in range(start):
                dp[i + 1][j + a[i + 1]] += dp[i][j]
                dp[i + 1][j] += dp[i][j]

        ans += dp[N - 1][start] * 6
    print(ans % mod)
    # print(start)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 998244353
ans = []

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

sumA = sum(a)

dp = [[0]*(sumA+301) for _ in range(N)]
start = (sumA+1)//2

dp[0][0] = 2
dp[0][a[0]] = 1

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

#print(dp)
out = sum(dp[N-1][start:])
ans = (3**N - out*3)%mod
#print(ans)

if sumA%2==0:
    dp = [[0]*(sumA+301) for _ in range(N)]
    dp[0][0] = 1
    dp[0][a[0]] = 1
    for i in range(N - 1):
        for j in range(start):
            dp[i+1][j+a[i+1]] += dp[i][j]
            dp[i+1][j] += dp[i][j]

    ans += dp[N-1][start]*6
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 998244353
ans = []

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

sumA = sum(a)

dp = [[0]*(sumA+301) for _ in range(N)]
start = (sumA+1)//2

dp[0][0] = 2
dp[0][a[0]] = 1

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

#print(dp)
out = sum(dp[N-1][start:])
ans = (3**N - out*3)%mod
#print(ans)

if sumA%2==0:
    dp2 = [[0] * (sumA + 1) for _ in range(N)]
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(N - 1):
        for j in range(start):
            dp2[i+1][j+a[i+1]] += dp2[i][j]
            dp2[i+1][j] += dp2[i][j]

    ans += dp2[N-1][start]*6
print(ans%mod)
#print(start)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 998244353
inf = float('inf')
ans = []

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

sumA = sum(a)

dp = [[0]*(sumA+1) for _ in range(N)]
start = (sumA+1)//2

dp[0][0] = 2
dp[0][a[0]] = 1

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

#print(dp)
out = sum(dp[N-1][start:])
ans = (3**N - out*3)%mod
#print(ans)

if sumA%2==0:
    dp2 = [[0] * (sumA + 1) for _ in range(N)]
    dp2[0][0] = 1
    dp2[0][a[0]] = 1
    for i in range(N - 1):
        for j in range(start):
            dp2[i+1][j+a[i+1]] += dp2[i][j]
            dp2[i+1][j] += dp2[i][j]

    ans += dp2[N-1][start]*6
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 998244353
inf = float('inf')
ans = []

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

sumA = sum(a)

dp = [[0]*(sumA+1) for _ in range(N)]
start = (sumA+1)//2

dp[0][0] = 2
dp[0][a[0]] = 1

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

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

#print(dp)
out = sum(dp[N-1][start:])
ans = (3**N - out*3)%mod
#print(ans)

if sumA%2==0:
    ans += dp2[N-1][sumA//2]*3
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 998244353
inf = float('inf')
ans = []

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

sumA = sum(a)

dp = [[0]*(sumA+1) for _ in range(N)]
start = (sumA+1)//2

dp[0][0] = 2
dp[0][a[0]] = 1

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

#print(dp)
out = sum(dp[N-1][start:])
ans = (3**N - out*3)%mod
#print(ans)

if sumA%2==0:
    dp = [[0] * (sumA + 1) for _ in range(N)]
    dp[0][0] = 1
    dp[0][a[0]] = 1

    for i in range(N - 1):
        for j in range(sumA - a[-1] + 1):
            if j <= sumA - a[i + 1]:
                dp[i + 1][j + a[i + 1]] += dp[i][j]
            dp[i + 1][j] += dp[i][j]
    ans += dp[N-1][sumA//2]*3
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
#最後に６倍
#数列を三つに分けて三角形にできるかどうか

n,*l=map(int,open(0).read().split())

mod=998244353

def dfs(i,a,b,c):
    i+=1
    if i==n:
        if a>0 and b>0 and c>0:
            a,b,c=sorted((a,b,c))
            return a+b>c
        else:
            return 0
    return dfs(i,a+l[i],b,c)%mod + dfs(i,a,b+l[i],c)%mod + dfs(i,a,b,c+l[i])%mod
i=-1
print(dfs(i,0,0,0))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
mod=998244353
A=[]
for i in range(n):
  A.append(int(input()))
t=sum(A)
DP=[[0]*(t) for _ in range(n+1)]
DP[0][0]=1
for i in range(n):
  a=A[i]
  for j in range(t):
    DP[i+1][j]=(2*DP[i][j]+DP[i][max(0,j-a)])%mod

DP2=[[0]*(t) for _ in range(n+1)]
DP2[0][0]=1
for i in range(n):
  a=A[i]
  for j in range(t):
    if j>=a:
      DP2[i+1][j]=(DP2[i][j]+DP2[i][j-a])%mod
    else:
      DP2[i+1][j]=DP2[i][j]

ans=1
for i in range(n):
  ans=(ans*3)%mod
if t%2==1:
  print((ans-3*DP[n][t//2+1])%mod)
else:
  print((ans-3*DP[n][t//2]+3*DP2[n][t//2])%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n = int(input())
dp_dic = { (0,0,0) : 1 }
for _ in range(n):
    a = int(input())
    new_dp_dic = {}
    for j in dp_dic:
        if (j[0]+a,j[1],j[2]) in new_dp_dic:
            new_dp_dic[(j[0]+a,j[1],j[2])] += dp_dic[(j[0],j[1],j[2])]
            new_dp_dic[(j[0]+a,j[1],j[2])] %= mod
        else:
            new_dp_dic[(j[0]+a,j[1],j[2])] = dp_dic[(j[0],j[1],j[2])]
        if (j[0],j[1]+a,j[2]) in new_dp_dic:
            new_dp_dic[(j[0],j[1]+a,j[2])] += dp_dic[(j[0],j[1],j[2])]
            new_dp_dic[(j[0],j[1]+a,j[2])] %= mod
        else:
            new_dp_dic[(j[0],j[1]+a,j[2])] = dp_dic[(j[0],j[1],j[2])]
        if (j[0],j[1],j[2]+a) in new_dp_dic:
            new_dp_dic[(j[0],j[1],j[2]+a)] += dp_dic[(j[0],j[1],j[2])]
            new_dp_dic[(j[0],j[1],j[2]+a)] %= mod
        else:
            new_dp_dic[(j[0],j[1],j[2]+a)] = dp_dic[(j[0],j[1],j[2])]
    dp_dic = new_dp_dic

def make_triangle(a,b,c):
    x, y, z = sorted([a,b,c])
    if z < y + x:
        return True
    else:
        return False
ans = 0
for i in dp_dic:
    if make_triangle(i[0],i[1],i[2]):
        ans += dp_dic[i]
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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




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

    mod = 998244353

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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




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

    mod = 998244353

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    a,b,c = LI()
    if min(a,b) < c < max(a,b):
        print("Yes")
    else:
        print("No")
    return

#B
def B():
    n = I()
    s = S()
    k = I()
    f = s[k-1]
    for i in range(n):
        if s[i] != f:
            print("*",end = "")
        else:
            print(s[i],end = "")
    print()
    return

#C
def C():
    n = I()
    s = S()
    ans = 0
    f = [0]*(n+1)
    for i in range(n):
        f[i+1] = 1 if s[i] == "#" else 0
    for i in range(n):
        f[i+1] += f[i]
    ans = float("inf")
    for i in range(n+1):
        ans = min(ans, f[i]+(n-i)-f[n]+f[i])
    print(ans)
    return

#D
def D():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod
    mod = 998244353
    n = I()
    fact = [1]
    for i in range(1000):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*1001
    inv[1000] = pow(fact[1000], mod-2, mod)
    for i in range(1000)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    a = IR(n)
    m = sum(a)
    dp = defaultdict(int)
    dp[(0,0)] = 1
    for i in range(n):
        ai = a[i]
        d = list(dp.items())
        for (k,j),l in d:
            nk,nj = k+1,j+ai
            dp[(nk,nj)] += l
            if dp[(nk,nj)] >= mod:
                dp[(nk,nj)] %= mod
    ans = pow(3,n,mod)
    k = m/2
    for i,j in dp.keys():
        if j >= k:
            ans -= 3*dp[(i,j)]*pow(2,n-i,mod)%mod
            if j == k:
                ans += 3*dp[(i,j)]%mod
            ans %= mod
    print(ans)
    return

#E
def E():
    n,m,k = LI()
    a = LI()
    if k == 1:
        if m == n:
            print(sum(a))
        else:
            print(-1)
        return
    dp = [[-float("inf")]*(m+1) for i in range(n+1)]
    dp[0][0] = 0
    for i in range(1,n+1):
        for j in range((i-1)//k,min(m,i)):
            res = 0
            for l in range(max(0,i-k),i):
                if dp[l][j] > res:
                    res = dp[l][j]
            res += a[i-1]
            if res > dp[i][j+1]:
                dp[i][j+1] = res
    ans = -float("inf")
    for i in range(k):
        if dp[-i-1][m] > ans:
            ans = dp[-i-1][m]
    if ans < 0:
        print(-1)
        return
    print(ans)
    return

#F
def F():
    n,a,b = LI()
    d = LI()
    d.sort()
    d.insert(0,0)
    d.append(n+1)
    ans = -1
    for i in range(b+1):
        ans += 1+(d[i+1]-d[i]-1)//a
    print(n-ans)
    return

#G
def G():
    ma = 1000
    d = [0]*ma
    p = 2
    prime = []
    while 1:
        while d[p]:
            p += 1
            if p >= ma:
                break
        if p >= ma:
            break
        prime.append(p)
        j = p
        while j < ma:
            d[j] = 1
            j += p
    def IsPrime(n):
        i = 0
        while i < len(prime):
            if n%prime[i] == 0:
                return 0
            i += 1
        return 1
    def f(a,b):
        res = 0
        for i in range(a,b+1):
            res += IsPrime(i)
        return res
    mi = 9*10**15
    ma = 10**16-2018
    a = 9*10**15
    b = a+2018
    ans = [f(a,b),a,b]
    for i in range(10000):
        a = random.randint(mi,ma)
        b = a+2018
        m = f(a,b)
        if m > ans[0]:
            ans = [m,a,b]
    print(*ans)
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Time Limit Exceeded

Solution code:
DVSR = 998244353
def POW(x, y): return pow(x, y, DVSR)
def INV(x, d=DVSR): return pow(x, d - 2, d)
def DIV(x, y, d=DVSR): return (x * INV(y, d)) % d
def LI(): return [int(x) for x in input().split()]
def II(): return int(input())

N = int(input())
INL = [II() for _ in range(N)]
SM = sum(INL)
HSM = SM//2

DP1 = [[0]*(SM+1) for _ in range(N+1)]
DP2 = [[0]*(SM+1) for _ in range(N+1)]
DP1[0][0] = 1
DP2[0][0] = 1

for i, value in enumerate(INL,1):
    for j in range(SM+1):
        if j-value >= 0:
            DP1[i][j] = (2*DP1[i-1][j]+DP1[i-1][j-value])%DVSR
            DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-value]
        else:
            DP1[i][j] = (2*DP1[i-1][j])%DVSR
            DP2[i][j] = DP2[i-1][j]

sub = 0
patall = POW(3, N)
for i in range(HSM+1, SM+1):
    sub += DP1[N][i]*3

if SM % 2 == 0:
    sub += 3*(DP1[N][HSM] - 2*DP2[N][HSM])
    sub += 3*DP2[N][HSM]

# print(DP2[N])
# print(SM)
print((patall - sub) % DVSR)

Submission status: Time Limit Exceeded

Solution code:
N =  int(input())

a = [0 for i in range(N)]

mod = 998244353
ans = pow(3, N, mod)

dp = [[0 for i in range(N*300+1)] for j in range(N+1)]
dp[0][0] = 1

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

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

tmp = 0
for i in range(sum//2 + (sum&1), sum+1):
    tmp += dp[N][i]
    tmp %= mod

ans = ans + mod - tmp * 3
ans %= mod

if not(sum & 1):
    dp = [[0 for i in range(N*300+1)] for j in range(N+1)]
    dp[0][0] = 1
    sum = 0
    for i in range(0, N):
        sum += a[i]
        for j in range(sum+1):
            dp[i+1][j] += dp[i][j]
            dp[i+1][j] %= mod
            dp[i+1][j + a[i]] = dp[i][j]
            dp[i+1][j + a[i]] %= mod
    ans += dp[N][sum >> 1] * 3
    ans %= mod

print(ans)