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:
import math

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

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

memo=[[[[ -1 for _ in range(math.ceil(half))] for _ in range(math.ceil(half))] for _ in range(math.ceil(half))] for _ in range(n)]
#print(memo[0][0][0][0])
def f(r,g,b,cur):
    if r >= half or g >= half or b >= half:
        return 0
    if cur == n:
        return 1
    tmp = sorted([r,g,b])
    m1 = tmp[2]
    m2 = tmp[1]
    m3 = tmp[0]
    if memo[cur][m1][m2][m3] != -1:
        return memo[cur][m1][m2][m3]
    memo[cur][m1][m2][m3] = (f(r + arr[cur], g, b, cur+1) + f(r, g+arr[cur], b, cur+1) + f(r, g, b+arr[cur], cur+1)) % 998244353
    return memo[cur][m1][m2][m3]

print(f(0,0,0,0))

Submission status: Time Limit Exceeded

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

vals = sorted(vals)
ans_dict={}
rest_vals = [sum(vals[i:]) for i in range(N)]

def is_ok(r,g,b):
	max_val = max(r,g,b)
	if max_val < r+g+b - max_val:
		return 1
	else:
		return 0

def calc(i,r,g,b):
	if (i,r,g,b) in ans_dict.keys():
		return ans_dict[(i,r,g,b)]
	
	if i == N -1:
		ret =  is_ok(r+vals[N-1],g          ,b)
		ret += is_ok(r          ,g+vals[N-1],b)
		ret += is_ok(r          ,g          ,b+vals[N-1])
		ans_dict[(i,r,g,b)] = ret
		return ret
	
	tmp =  is_ok(r+rest_vals[i],g             ,b)
	tmp += is_ok(r             ,g+rest_vals[i],b)
	tmp += is_ok(r             ,g             ,b+rest_vals[i])
	if tmp == 3:
		ret = 3 ** (N-i)
		ans_dict[(i,r,g,b)] = ret
		return ret
		
	ret =  calc(i+1,r+vals[i],g        ,b)
	ret += calc(i+1,r        ,g+vals[i],b)
	ret += calc(i+1,r        ,g        ,b+vals[i])
	ans_dict[(i,r,g,b)] = ret
	return ret

print(calc(0,0,0,0) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

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[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

#    memo[(a, b, c, i)] = ret
    return ret

print(dfs(0, 0, 0, 0))

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

memo=[[[[ -1 for _ in range(math.ceil(half))] for _ in range(math.ceil(half))] for _ in range(math.ceil(half))] for _ in range(n)]
#print(memo[0][0][0][0])
def f(r,g,b,cur):
    if r >= half or g >= half or b >= half:
        return 0
    if cur == n:
        return 1
    if memo[cur][r][g][b] != -1:
        return memo[cur][r][g][b]
    memo[cur][r][g][b] = (f(r + arr[cur], g, b, cur+1) + f(r, g+arr[cur], b, cur+1) + f(r, g, b+arr[cur], cur+1)) % 998244353
    return memo[cur][r][g][b]

print(f(0,0,0,0))

Submission status: Time Limit Exceeded

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

state = {(0,0):1}

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

ans = 0
total = sum(a)
for x, j in state.items():
    c = total-x[0]-x[1]
    if x[0]!=0 and x[1]!=0 and c!=0\
       and x[0]<x[1]+c\
       and x[1]<x[0]+c\
       and c<x[0]+x[1]:       
        ans = (ans+j)%998244353

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

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[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

    memo[(a, b, c, i)] = ret
    return ret

print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import defaultdict

N = int(input())
#N = 5
import random
X = []
for _ in range(N):
    X.append(int(input()))
    #X.append(random.randint(1, 300))
X = sorted(X, reverse=True)
total = sum(X)

memo = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: -1)))
def recursive(i, r, g, b):
    if i == N:
        if max(r, g, b) < total / 2:
            return 1
        else:
            return 0
            
    if max(r, g, b) >= total / 2:
        return 0
     
    #r2, g2, b2 = sorted([r, g, b])
    #if memo[r2][g2][b2] != -1:
    #    return memo[r2][g2][b2]
    if memo[r][g][b] != -1:
        return memo[r][g][b]
        
    count = 0
    count += recursive(i + 1, r + X[i], g, b)
    count += recursive(i + 1, r, g + X[i], b)
    count += recursive(i + 1, r, g, b + X[i])
    
    memo[r][g][b] = count
    memo[r][b][g] = count
    memo[g][r][b] = count
    memo[g][b][r] = count
    memo[b][r][g] = count
    memo[b][g][r] = count
    
    return count
    
print(recursive(0, 0, 0, 0) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import numpy as np

n=int(input())  #数値入力

list_a = []
for i in range(n):
    list_a.append(int(input()))
    
arr_a = np.array(list_a)

A = (0,1,2)
perm = list(itertools.product(A, repeat=n))

def sankaku(p):
    if min([p.count(0), p.count(1), p.count(2)]) == 0:
        return 0
    
    sum_0 = np.array(list_a)[np.where(np.array(p)==0)[0]].sum()
    sum_1 = np.array(list_a)[np.where(np.array(p)==1)[0]].sum()
    sum_2 = np.array(list_a)[np.where(np.array(p)==2)[0]].sum()
    
    if (sum_0 + sum_1 > sum_2) & (sum_0 + sum_2 > sum_1) & (sum_1 + sum_2 > sum_0):
        return 1
    else:
        return 0
    
sum_p = 0
for p in perm:
    sum_p += sankaku(p)
    
print(sum_p)

Submission status: Time Limit Exceeded

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] = (new_state[n]+j)%998244353
    new_state, state = state, new_state

ans = 0
for x, j in state.items():
    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:
n=int(input())
a=[]
for _ in [0]*n:
    a.append(int(input()))
a_all=sum(a)
d={}
def an(i,r,g,b):
    if r>=a_all/2 or g>=a_all/2 or b>=a_all/2 :
        return 0
    if i==n:
        return 1
    else:
        key="*".join([str(x) for x in (i,r,g,b)])
        if key not in d.keys():
            d[key]=an(i+1,r+a[i],g,b)+an(i+1,r,g+a[i],b)+an(i+1,r,g,b+a[i])
        return d[key]
    
ans=an(0,0,0,0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def f(a,b,c,cur):
    if max(a,b,c)>lim:
        return 0
    if cur==n:
        return 1
    t=(a,b,c,cur)
    if t in memo:
        return memo[t]
    re1=f(a+ms[cur],b,c,cur+1)
    re2=f(a,b+ms[cur],c,cur+1)
    re3=f(a,b,c+ms[cur],cur+1)
    re=re1+re2+re3
    memo[t]=re
    return re

memo={}
n=int(sys.stdin.readline())
ms=[]
for i in range(n):
    ms+=[int(sys.stdin.readline())]
lim=(sum(ms)-1)//2
print(f(ms[0],0,0,1)*3%998244353)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!

from collections import defaultdict

N = int(input())

X = []
for _ in range(N):
    X.append(int(input()))
 
memo = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: -1)))
def recursive(i, r, g, b):
    if i == N:
        if max(r, g, b) < (r + g + b) / 2:
            return 1
        else:
            return 0
    if memo[r][g][b] != -1:
        return memo[r][g][b]
        
    count = 0
    count += recursive(i + 1, r + X[i], g, b)
    count += recursive(i + 1, r, g + X[i], b)
    count += recursive(i + 1, r, g, b + X[i])
    
    memo[r][g][b] = count
    
    return count
    
print(recursive(0, 0, 0, 0) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

def f(a,b,c,cur):
    if max(a,b,c)>lim:
        return 0
    if cur==n:
        return 1
    t=(a,b,c,cur)
    if t in memo:
        return memo[t]
    re1=f(a+ms[cur],b,c,cur+1)
    re2=f(a,b+ms[cur],c,cur+1)
    re3=f(a,b,c+ms[cur],cur+1)
    re=re1+re2+re3
    memo[t]=re
    return re

memo={}
n=int(sys.stdin.readline())
ms=[]
for i in range(n):
    ms+=[int(sys.stdin.readline())]
lim=(sum(ms)-1)//2
print(f(0,0,0,0)%998244353)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np
MOD = 998244353
N = int(input())
A = [int(input()) for _ in range(N)]
S = sum(A)
dp = np.zeros(S+1, dtype=np.int64)
dp[0] = 1
for a in A:
    prev = dp
    dp = prev * 2
    dp[a:] += prev[:-a]
    dp %= MOD
ans = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] += dp.copy()[:-a]
        dp %= MOD
    ans += dp[S//2] * 3
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
from numpy import zeros, roll

mod = 998244353

N, *A = map(int, open(0))

S = sum(A)

dp1 = zeros(S + 1, dtype=int)
dp1[0] = 1

dp2 = zeros(S + 1, dtype=int)
dp2[0] = 1

for a in A:
    dp1 = (2 * dp1 + roll(dp1, a)) % mod
    dp2 = (dp2 + roll(dp2, a)) % mod

M = (S + 1) // 2

res = 3 * dp1[M:].sum()
if S % 2 == 0:
    res -= 3 * dp2[M]

print((pow(3, N, mod) - res) % mod)

Submission status: Accepted

Solution code:
n = int(input())
A = tuple(int(input()) for _ in range(n))
S = sum(A)
mod = 998244353
ans = pow(3, n, mod)
cnt = 0
dp = [[0]*(S+1) for _ in range(n+1)]
dp[0][0] = 1
for i, a in enumerate(A):
  for k in range(S+1):
    if k >= a:
      dp[i+1][k] = dp[i][k]*2 + dp[i][k-a]
    else:
      dp[i+1][k] = dp[i][k]*2
    dp[i+1][k] %= mod
for k in range((S+1)//2, S+1):
  ans -= dp[n][k]*3
  ans %= mod
if S%2 == 0:
  dp = [0]*(S//2+1)
  dp[0] = 1
  for i, a in enumerate(A):
    for k in range(S//2, -1, -1):
      if k >= a:
        dp[k] += dp[k-a]
  ans += dp[S//2]*3
  ans %= mod
print(ans)

Submission status: Accepted

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


N = I()
A = [0] + [I() for _ in range(N)]
s = sum(A)
mod = 998244353

dp1 = [[0]*(s+1) for _ in range(N+1)]  # dp[i][j] = a1~aiを塗った時に、赤で塗った和をjにする方法数
dp1[0][0] = 1
for i in range(1,N+1):
    a = A[i]
    for j in range(s+1):
        if j >= a:
            dp1[i][j] = dp1[i-1][j]*2 + dp1[i-1][j-a]
        else:
            dp1[i][j] = dp1[i-1][j]*2
        dp1[i][j] %= mod

dp2 = [[0]*(s//2+1) for _ in range(N+1)]  # dp[i][j] = a1~aiの中からいくつか選んで、和をjにする方法数
dp2[0][0] = 1
for i in range(1,N+1):
    a = A[i]
    for j in range(s//2+1):
        if j >= a:
            dp2[i][j] = dp2[i-1][j] + dp2[i-1][j-a]
        else:
            dp2[i][j] = dp2[i-1][j]
        dp2[i][j] %= mod

a = sum(dp1[N][i] for i in range((s+1)//2,s+1))
a %= mod
if s % 2 == 0:
    a -= dp2[N][s//2]

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = [int(input()) for _ in range(n)]
M = 998244353
s = sum(a)
l = s//2 + int(s%2==1)
# dp = [[0]*(s+1) for _ in range(n+1)]
dp = [0]*(s+1)
dp2 = [0]*(s+1)
dp[0] = pow(2, n, M)
dp2[0] = 1
inv2 = pow(2, M-2, M)
for i in range(1,n+1):
    num = a[i-1]
    for j in range(s, -1, -1):
        if j>=num:
            dp[j] += dp[j-num]*inv2
            dp[j] %= M
            dp2[j] += dp2[j-num]
            dp2[j] %= M
val = sum(dp[i] for i in range(l, s+1)) * 3
if s%2==0:
    val -= dp2[s//2]*3
ans = (pow(3,n,M) - val)%M
print(ans%M)

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=998244353

    """
    aiが300以下なのが嬉しい，総和でなんかできる．
    dp[i][j]でi番目まで見て合計がj，j<=N*max(a)なので合計O(N^2 max(a))，これでRの通り数が求まるがGB用に何が残っているのかわからん-
    余事象，R>=sum(a)/2 ならダメなわけで
    
    """
    N=I()
    A=[0]*N
    for i in range(N):
        A[i]=I()
    
    S=sum(A)
    
    dp=[[0]*(S+1) for _ in range(N+1)]
    # i番目まで見て，Rの総和がjの通り数
    dp[0][0]=1
    
    for i in range(N):
        a=A[i]
        for j in range(S+1):
            dp[i+1][j]=(dp[i+1][j] + dp[i][j]*2)%mod#g,b
            if j+a<=S:
                dp[i+1][j+a]=(dp[i+1][j+a] + dp[i][j])%mod#r
    
    rem=0
    for j in range((S+1)//2,S+1):
        rem=(rem+dp[-1][j])%mod#RがS/2以上なら基本的に被りを考慮する必要はない
    ans=pow(3,N,mod)-rem*3#r,g,b3色分
    ans%=mod#負数防止
        
    if S%2==0:
        # 0,S/2,S/2は被って数えている，bを使わないバージョン
        dp2=[[0]*(S+1) for _ in range(N+1)]
        # i番目まで見て，Rの総和がjの通り数
        dp2[0][0]=1
        
        for i in range(N):
            a=A[i]
            for j in range(S+1):
                dp2[i+1][j]=(dp2[i+1][j] + dp2[i][j])%mod#g
                if j+a<=S:
                    dp2[i+1][j+a]=(dp2[i+1][j+a] + dp2[i][j])%mod#r
                    
        temp=dp2[-1][S//2]
        ans+=temp*3
        
    
    print(ans%mod)
    
    # for i in range(N+1):
    #     print(dp[i])
            

main()

Submission status: Accepted

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

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

ans = pow(3, N, mod)
S = sum(a)
M = 300 * N

dp1 = [0] * (M + 1)
dp1[0] = 1
for i in a:
    ndp1 = [0] * (M + 1)
    for j in range(i, M + 1)[::-1]:
        ndp1[j] = (ndp1[j] + dp1[j - i]) % mod
    for j in range(M + 1):
        ndp1[j] = (ndp1[j] + dp1[j] * 2) % mod
    dp1 = ndp1
tmp = 0
for j in range((S + 1) // 2, M + 1):
    tmp = (tmp + dp1[j]) % mod
ans = (ans - 3 * tmp) % mod

dp2 = [0] * (2 * M + 1)
dp2[0] = 1
for i in a:
    ndp2 = [0] * (2 * M + 1)
    for j in range(i - M, M - i + 1):
        ndp2[j - i] = (ndp2[j - i] + dp2[j]) % mod
        ndp2[j + i] = (ndp2[j + i] + dp2[j]) % mod
    dp2 = ndp2
ans = (ans + 3 * dp2[0]) % mod

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
mod=998244353
DP=[[0]*90001 for i in range(N+1)]
DP[0][0]=pow(2,N,mod)
inv2=((mod+1)>>1)
for i in range(N):
  for j in range(300*i+1):
    DP[i+1][j]=(DP[i][j]+DP[i+1][j])%mod
    DP[i+1][j+A[i]]=DP[i][j]*inv2%mod
P=(pow(3,N,mod)-sum(DP[N][((sum(A)+1)>>1):])*3)%mod
DP=[[0]*90001 for i in range(N+1)]
DP[0][0]=1
for i in range(N):
  for j in range(300*i+1):
    DP[i+1][j]=(DP[i][j]+DP[i+1][j])%mod
    DP[i+1][j+A[i]]=DP[i][j]%mod
if sum(A)&1==0:
  P+=DP[N][sum(A)>>1]*3
print(P%mod)

Submission status: Accepted

Solution code:
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [0] * (s * 2 + 1)
# dp[s+i] ... count of i = B - R - G
dp[s] = 1
for ai in a:
    ndp = [0] * (s * 2 + 1)
    for j in range(s * 2 + 1):
        if dp[j] != 0:
            ndp[j+ai] += dp[j]
            ndp[j+ai] %= MOD
            ndp[j-ai] += dp[j] * 2
            ndp[j-ai] %= MOD
    dp = ndp
# exclude B >= R + G
# beware cases like B == R and G == 0

# dp2[s+i] ... count of i = B - R, assuming G is always 0
dp2 = [0] * (s * 2 + 1)
dp2[s] = 1
for ai in a:
    ndp2 = [0] * (s * 2 + 1)
    for j in range(s * 2 + 1):
        if dp2[j] != 0:
            ndp2[j+ai] += dp2[j]
            ndp2[j+ai] %= MOD
            ndp2[j-ai] += dp2[j]
            ndp2[j-ai] %= MOD
    dp2 = ndp2
#print(sum(dp[s+1:]), sum(dp2[s+1:]))
ans = (pow(3, n, MOD) - ((sum(dp[s:]) - dp2[s] * 2) * 3 + dp2[s] * 3)) % MOD
print(ans)

Submission status: Accepted

Solution code:

mod =998244353

def main():
    #start coding here...
    #Three colors
    N=int(input())
    A=[int(input()) for i in range(N)]
    M=(sum(A)-1)//2
    S=sum(A)
    # 1<= R,G,B<= S, R+ G + B = S
    #ほうじょ原理
    Alls = pow(3,N,mod) 
    # R,G,B　のうち1つ以上が S より大のケース case2
    case2=0
    #dp[x][i] := 初めのｘこを塗り分けて、Rの値がiになるものの個数
    dp=[[0 for i in range(90001)] for j in range(N+1)]
    dp[0][0]=1
    for i in range(1,N+1):
        v=A[i-1]
        for j in range(90001):
            if j>=v:
                dp[i][j]= dp[i-1][j-v]+ 2*dp[i-1][j]
            else:
                dp[i][j]=2*dp[i-1][j]
            dp[i][j]%=mod   

    if S%2!=0:
        # R,G,B のうち1つだけがSより大きい
        for i in range(M+1,90001):
            case2+=3*dp[N][i]
            case2%=mod
    if S%2==0:
        #R,G,B のうち1つがSより大きい
        for i in range(M+1,90001):
            case2+=3*dp[N][i]
            case2%=mod
        #R,G,B のうち2つがS//2
        #sub_dp[x][v]:= 初めのxこを塗り分けて　Rの方をvにする方法
        sub_dp=[[0 for i in range(90001)] for j in range(N+1)]
        sub_dp[0][0]=1
        for i in range(1,N+1):
            v=A[i-1]
            for j in range(90001):
                if j>=v:
                    sub_dp[i][j]= sub_dp[i-1][j]+sub_dp[i-1][j-v]
                else:
                    sub_dp[i][j]=sub_dp[i-1][j]
                sub_dp[i][j]%=mod
        case2-=3*sub_dp[N][S//2]
        case2%=mod
    ans=Alls-case2
    print(ans%mod)
    return
        


if __name__ =="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
mod = 998244353
dp = [0] * 900001
dp2 = [0] * 900001
dp[0] = 1
dp2[0] = 1
sm = 0
for _ in range(N):
  x = int(input())
  for y in range(900000, -1, -1):
    if dp[y]:
      dp[x + y] += dp[y]
      dp[x + y] %= mod
      dp2[x + y] += dp2[y]
      dp2[x + y] %= mod
      dp[y] *= 2
      dp[y] %= mod
  sm += x
res = 0
for x in range(sm + 1):
  if x > sm - x:
    res += max(0, dp[x])
    res %= mod
  elif x == sm - x:
    res += dp[x] - dp2[x]
    res %= mod

print((pow(3, N, mod) - res * 3) % mod)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,read().split()))
mod = 998244353

sum_a = sum(a)
dp = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rg = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_rb = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r = [ [0] * (sum_a+1) for _ in range(n+1)]
dp_r[0][0] = 1
tot = 0

for i in range(1,n+1):
    ai = a[i-1]
    tot += ai
    for j in range(tot+1):
        dp_rg[i][j] += dp_rg[i-1][j] + dp_r[i-1][j]
        dp_rb[i][j] += dp_rb[i-1][j] + dp_r[i-1][j]
        dp[i][j] += dp[i-1][j] * 2 + dp_rb[i-1][j] + dp_rg[i-1][j]

        if(j >= ai):
            dp_r[i][j] += dp_r[i-1][j-ai]
            dp_rg[i][j] += dp_rg[i-1][j-ai]
            dp_rb[i][j] += dp_rb[i-1][j-ai]
            dp[i][j] += dp[i-1][j-ai]
        dp_rg[i][j] %= mod
        dp_rb[i][j] %= mod
        dp[i][j] %= mod

r_over = sum(dp[-1][(1+sum_a)//2:]) % mod
ans = (pow(3,n,mod) - 3*pow(2,n,mod) + 3 - 3*r_over)%mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    n = int(input())
    a = sorted([int(input()) for _ in [0]*n])
    dp = np.array([1], dtype=np.int64)
    DP = np.array([1], dtype=np.int64)
    s = 1
    mod = 998244353
    for i in a:
        dp2 = np.concatenate([dp, np.zeros(i, dtype=np.int64)])
        DP2 = np.concatenate([DP, np.zeros(i, dtype=np.int64)])
        dp2[i:] = (dp2[i:]+2*dp) % mod
        DP2[i:] = (DP2[i:]+DP) % 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: Accepted

Solution code:
N=int(input())
A=[]
for i in range(N):
    A.append(int(input()))
mod=998244353
inv=pow(2,mod-2,mod)
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,A[i]-1,-1):
        dp[j]=(dp[j]+inv*dp[j-A[i]])%mod
        sub[j]=(sub[j]+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: Accepted

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

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

dp2=[[0]*(s+1) for _ in range(n)]
dp2[0][0]=1;dp2[0][a[0]]=1
for i in range(n-1):
    for j in range(s+1):
        dp2[i+1][j]=(dp2[i+1][j]+dp2[i][j])%mod
        if j+a[i+1]<=s: dp2[i+1][j+a[i+1]]=(dp2[i+1][j+a[i+1]]+dp2[i][j])%mod

if s%2==0:
    inable=( sum(dp[n-1][s//2:]) - dp2[n-1][s//2] )*3%mod
else:
    inable=( sum(dp[n-1][s//2+1:]) )*3 %mod

ans=1
for _ in range(n):
    ans=ans*3%mod
ans=(ans-inable)%mod
print(ans)

Submission status: Accepted

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
        nlis[j] %= mod
        if j+a[i] <= asum:
            nlis[j+a[i]] += lis[j]
            nlis[j+a[i]] %= mod

    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: Accepted

Solution code:
mod = 998244353
N = int(input())
a = [int(input()) for _ in range(N)]
s = sum(a)
dp = [[0]*(s+1) for _ in range(N)]
dp2 = [[0]*(s+1) for _ in range(N)]
dp2[0][0] = 1
dp2[0][a[0]] = 1
dp[0][0] = 1
dp[0][a[0]] = 2
for i in range(1, N):
    for j in range(s+1):
        dp[i][j] = dp[i-1][j]
        dp2[i][j] = dp2[i-1][j]
        if j-a[i]>=0:
            dp[i][j]+=dp[i-1][j-a[i]]*2
            dp2[i][j] += dp2[i-1][j-a[i]]
        dp[i][j]%=mod
        dp2[i][j]%=mod
if s%2 == 0:
    ans = pow(3, N, mod)-sum(dp[-1][:s//2+1])*3+dp2[-1][s//2]*3
else:
    ans = pow(3, N, mod)-sum(dp[-1][:s//2+1])*3
print(ans%mod)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()

mod=998244353

ans=pow(3,N,mod)
S=sum(A)
dp=[0]*(S+1)
dp[0]=1
for u in A:
    h=[0]*(S+1)
    for i in range(u):
        h[i]=2*dp[i]%mod
    for i in range(u,S+1):
        h[i]=(dp[i-u]+2*dp[i])%mod
    dp=h

ans=(ans-3*sum(dp[S-S//2:]))%mod

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
readline = sys.stdin.readline

MOD = 998244353
N = int(readline())
A = [int(readline()) for _ in range(N)]
S = sum(A)
C = Counter()
C[0] = 1
for a in A:
    for k, v in C.copy().items():
        C[k] = (C[k] + v)%MOD
        C[k+a] = (C[k+a] + v)%MOD
cnt = 0
for k, v in C.items():
    if 2*k >= S:
        cnt = (cnt + v)%MOD

cnt2 = 0
if S%2 == 0:
    D = Counter()
    D[0] = 1
    for a in A:
        for k, v in D.copy().items():
            D[k+a] = (D[k+a] + v)%MOD
    cnt2 = D[S//2]
ans = pow(3, N, MOD) - 3*cnt + 3*cnt2
print(ans%MOD)

Submission status: Accepted

Solution code:
import numpy as np
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 998244353
    n = int(input())
    mx = 90005
    dp = np.zeros(mx, dtype="i8")
    dp2 = np.zeros(mx, dtype="i8")
    dp[0] = 1
    dp2[0] = 1
    sum_a = 0
    for _ in range(n):
        a = int(input())
        sum_a += a
        dp[mx - 1:a - 1:-1] = dp[mx - 1:a - 1:-1] * 2 + dp[mx - a - 1::-1]
        dp[:a] *= 2
        dp %= md
        dp2[mx - 1:a - 1:-1] += dp2[mx - a - 1::-1]
        dp2 %= md
    ng = np.sum(dp[(sum_a + 1) // 2:]) - np.sum(dp2[(sum_a + 1) // 2:]) * 2 + 1
    ng %= md
    total = (pow(3, n, md) - 3 * pow(2, n, md) + 3) % md
    print((total - ng * 3) % md)
    # ALL-NG（NG…最大辺が周の半分以上になる）で求める
    # 最大辺を赤として、dp[r] 赤の和がrのパターンを求める
    # 「赤だけ」、「赤と他一色だけ」(両方dp2に含まれる)のパターンは除く必要がある
    # 赤の和が総和の半分以上になるパターンを考えるので、
    # 赤以外の色だけになるパターンは除く必要がない
    # その後、緑、青が最大の辺になる場合も考えて3倍

main()

Submission status: Accepted

Solution code:
# 2019-11-23 01:28:44(JST)
import sys
import numpy as np

MOD = 998244353

def main():
    n, *A = map(int, sys.stdin.read().split())
    S = sum(A)

    dp = np.zeros(S//2+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        dp[a:] = (dp[a:] + dp.copy()[:-a] * 2) % MOD
    
    ans = (pow(3, n, MOD) - dp.sum() * 3 % MOD) % MOD

    if S % 2 == 0:
        dp = np.zeros(S//2+1, dtype=np.int64)
        dp[0] = 1
        for a in A:
            dp[a:] = (dp[a:] + dp.copy()[:-a]) % MOD
        ans = (ans + dp[S//2] * 3) % MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
 
n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353
 
s = sum(aaa)
dp1 = np.zeros(s + 1, dtype=np.uint32)
dp2 = np.zeros(s + 1, dtype=np.uint32)
dp1[0] = 1
dp2[0] = 1
for a in aaa:
    dp1 = (dp1 * 2 + np.roll(dp1, a)) % MOD
    dp2 = (dp2 + np.roll(dp2, a)) % MOD
 
h = (s + 1) // 2
ans = (pow(3, n, MOD) - dp1[h:].sum() * 3) % MOD
if s % 2 == 0:
    ans = (ans + dp2[h] * 3) % MOD
print(int(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 18
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n = I()
A = IR(n)



a_sum = sum(A)
dp1 = [0] * (a_sum + 1)
dp1[0] = 1
dp2 = [0] * (a_sum + 1)
dp2[0] = 1
for i in range(n):
    for j in range(a_sum, -1, -1):
        if j < A[i]:
            dp2[j] = dp2[j] * 2 % mod
        else:
            dp1[j] = (dp1[j] + dp1[j - A[i]]) % mod
            dp2[j] = (dp2[j] * 2 + dp2[j - A[i]]) % mod


ans = pow(3, n, mod)
for k in range((a_sum + 1) // 2, a_sum + 1):
    ans = (ans - dp2[k] * 3) % mod


if a_sum % 2 == 0:
    ans = (ans + dp1[a_sum // 2] * 3) % mod


print(ans)