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

# 赤の和がS/2以上となるものを求めて3倍
# 和に対して何通りあるのか

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

answer = pow(3,N,MOD) - dp[(1+S)//2:].sum() * 3
# 2色が反例となる場合を引きすぎている
if S % 2 == 0:
    dp = np.zeros(S+1, dtype=np.int64)
    dp[0] = 1
    for a in A:
        prev = dp
        dp = prev # 赤以外を採用
        dp[a:] += prev[:-a] # 赤
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)

Submission status: Wrong Answer

Solution code:
import numpy as np

N =  int(input())

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

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

dp = np.zeros((N+1, N*300+1), dtype=np.int32)
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 = np.zeros((N+1, N*300+1), dtype=np.int32)
    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)

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

Solution code:
import numpy as np

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 = np.zeros((N, S + 1), dtype=np.int64)
count3[0, 0] = 2
count3[0, numbers[0]] = 1
count2 = np.zeros((N, S + 1), dtype=np.int64)
count2[0, 0] = 1
count2[0, numbers[0]] = 1

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

invalid_from = S // 2 + 1
if (S % 2 == 0):
  invalid_from = S // 2
count_invalid = np.sum(count3[N - 1, invalid_from:]) - 2 * np.sum(count2[N - 1, invalid_from:])
count_invalid %= M

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

Submission status: Wrong Answer

Solution code:
import numpy as np
N = int(input())
a = [int(input()) for _ in range(N)]
mod = 998244353
suma = sum(a)
memo = np.zeros((N+1, suma+1), dtype=np.int)
memo[0][0] = 1
memoe = np.zeros((N+1, suma+1), dtype=np.int)
memoe[0][0] = 1

ttl = 3
for i in range(N-1):
  ttl *=3
  ttl %= mod

for i in range(1, N+1):
  memotmp = memo[i-1]
  memotmp = np.concatenate((np.zeros((a[i-1]), dtype=np.int), memotmp),axis=1)
  memo[i] = (memo[i-1]*2 + memotmp[:suma+1])%mod
  memoe[i] = (memoe[i-1] + memotmp[:suma+1])%mod

ans = sum(memo[N][(suma-1)//2+1:])
if suma%2==0:
  ans -= memoe[N][suma/2]
  
print(((ttl - ans*3)%mod+mod)%mod)

Submission status: Wrong Answer

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+1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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+1)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

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

sumStart = 0
plus = 0

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

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

exceptCnt -= plus

print((TOTAL - exceptCnt) % MOD )

Submission status: Wrong Answer

Solution code:
import math

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

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

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

Submission status: Wrong Answer

Solution code:
import math

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

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

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

Submission status: Wrong Answer

Solution code:
import math

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

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

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

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)
m = 998244353
dp1 = np.zeros((N+1, s+1), dtype=np.int64)
dp1[0, 0] = 1
dp2 = np.zeros((N+1, s//2+1), dtype=np.int64)
dp2[0, 0] = 1
for i, ai in enumerate(a):
    dp1[i+1, :]   += dp1[i, :] * 2 % m
    dp1[i+1, ai:] += dp1[i, :-ai]
    dp2[i+1, :]   += dp2[i, :]
    dp2[i+1, ai:] += dp2[i, :-ai]
subset1 = np.sum(dp1[N, math.ceil(s/2):])
subset2 = 0 if s % 2 == 1 else dp2[N, s//2]
print((3 ** N - 3 * subset1 + 3 * subset2) % m)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)
m = 998244353
dp1 = np.zeros((N+1, s+1), dtype=np.int64)
dp1[0, 0] = 1
dp2 = np.zeros((N+1, s//2+1), dtype=np.int64)
dp2[0, 0] = 1
for i, ai in enumerate(a):
    dp1[i+1, :]   += dp1[i, :] * 2
    dp1[i+1, ai:] += dp1[i, :-ai]
    dp2[i+1, :]   += dp2[i, :]
    dp2[i+1, ai:] += dp2[i, :-ai]
subset1 = np.sum(dp1[N, math.ceil(s/2):])
subset2 = 0 if s % 2 == 1 else dp2[N, s//2]
print((3 ** N - 3 * subset1 + 3 * subset2) % m)

Submission status: Wrong Answer

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

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

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


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

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



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

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

print(ans)

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

N = int(input())
A = np.array([int(input()) for _ in range(N)])
S = np.sum(A)
MOD = 998244353


# dp0[i][j]: number of ways to obtain sum j for one of colors using first i integers.
# i = 0, 1, ..., N
# j = 0, 1, ..., S
dp0 = np.zeros((N + 1, S + 1), dtype=np.int64)

# dp1[i][j]: number of ways to obtain sum j for one of colors using first i integers,
#     but this time we use only TWO colors.
#     This will be used to find the number of cases when
#         (sum of R)= (sum of G) = S/2 & (sum of B) = 0 

dp1 = np.zeros((N + 1, S // 2 + 1), dtype=np.int64)

# using 0 integer to obtain sum=0
dp0[0, 0] = 1
dp1[0, 0] = 1


for i, x in enumerate(A):

    # If we do not use the next integer x, e.g. not for R, the sum of R is same, but possible ways are doubled
    #     because x can be used for either G or B
    dp0[i+1, :] += dp0[i, :] * 2 % MOD

    # Then we update the case when we use the next integer x.
    #     Lets say, sum=p was obtained for 4 different ways without using current integer x,
    #     then sum=p+x can also be obtained for 4 different ways.
    dp0[i+1, x:] += dp0[i, :-x]

    # If we do not use the next integer x, e.g. not for R, the sum of R is same, and possible ways are the same
    #     because this time we use only TWO colors. (say R and G, we dont use x for R, then automatically x goes for G)
    dp1[i + 1, :] += dp1[i, :]

    # Then we update the case when we use the next integer x.
    dp1[i+1, x:] += dp1[i, :-x]


# count cases: (R >= S / 2)
not_satisfy = np.sum(dp0[N][math.ceil(S/2):])

# count cases: (R = S / 2) & (B = S / 2)
double_reduct = 0 if S % 2 == 1 else dp1[N][S/2]

# total cases = 3 ** N

ans = 3 ** N - 3 * not_satisfy + 3 * double_reduct
print(ans % MOD)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
a = [0]
mod = 998244353
p = pow(3, n, mod)

for i in range(0, n):
    a.append(int(input()))

s = sum(a)
hs = math.ceil(s / 2)
dp = [[0 for j in range(0, s + 1)] for i in range(0, n + 1)]
dp[0][0] = 1

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

p = (p - 3 * sum(dp[n][hs:])) % mod

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

    for i in dp:
        print(i)

    p = (p + 3 * dp[n][hs]) % mod

print(p)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math

MOD = 998244353

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

S = sum(a)

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

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import math

MOD = 998244353

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

S = sum(a)

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

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

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

Submission status: Wrong Answer

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

MOD = 998244353

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

S = sum(a)

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

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

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

Submission status: Wrong Answer

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

MOD = 998244353

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

S = sum(a)

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

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

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

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

dp0 = np.zeros((N + 1, s + 1), dtype=np.int32)
dp0[0, 0] = 1
dp1 = np.zeros((N + 1, s // 2 + 1), dtype=np.int32)
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod

# Counts of (R >= s / 2)
c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))
# Counts of (R == s / 2 and G == s / 2)
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

total = sum(ms)
dp = np.zeros(total + 1, dtype=np.int64)
dp[0] = 1

for m in ms:
    dp[m:] = (dp[m:] * 2 + dp[:-m])% 998244353
    dp[:m] *= 2

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

if total % 2 == 0:
    dp2 = np.zeros(total // 2 + 1, dtype=np.int64)
    dp2[0] = 1
    for m in ms:
        dp2[m:] = dp2[m:] + dp2[:-m]
    yo -= dp2[-1] * 3

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

Submission status: Wrong Answer

Solution code:
import math
import numpy as np

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

# Counts of (R >= s / 2)
dp0 = np.zeros((N + 1, s + 1))
dp0[0, 0] = 1
# Counts of (R == s / 2 and G == s / 2)
dp1 = np.zeros((N + 1, s + 1))
dp1[0, 0] = 1

for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2
    dp0[i + 1, x:] += dp0[i, :-x]
    dp1[i + 1, :] += dp1[i, :]
    dp1[i + 1, x:] += dp1[i, :-x]

c0 = int(np.sum(dp0[N][math.ceil(s / 2):s+2]))
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

total = sum(ms)
dp = np.zeros(total + 1, dtype=np.int64)
dp[0] = 1

for m in ms:
    dp[m:] = dp[m:] * 2 + dp[:-m]
    dp[:m] *= 2

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

if total % 2 == 0:
    dp2 = np.zeros(total // 2 + 1, dtype=np.int64)
    dp2[0] = 1
    for m in ms:
        dp2[m:] = dp2[m:] + dp2[:-m]
    yo -= dp2[-1] * 3

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

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

total=sum(ms)
dp=np.zeros(total+1,dtype=np.int64)
dp[0]=1

for m in ms:
    dp[m:]=dp[m:]*2+dp[:-m]
    dp[:m]*=2

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

if total%2==0:
    dp2 = np.zeros(total//2 + 1, dtype=np.int64)
    dp2[0] = 1
    for m in ms:
        dp2[m:] += dp2[:-m]
    yo-=dp2[-1]*3

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

Submission status: Wrong Answer

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

s = sum(a)
mod = 998244353

dp1 = [0] * (s+1)
dp2 = [0] * (s+1)
dp1[0] = 1
dp2[0] = 1
sum_ = 0


ans = 0
for n in range(N):
    for i in reversed(range(sum_+1)):
        dp1[i] %= mod
        dp2[i] %= mod
        dp1[i+a[n]] += dp1[i]
        dp1[i] <<= 1
        dp2[i+a[n]] += dp2[i]
    print(dp1,dp2)
    sum_ += a[n]

ans = (3 ** N)%mod
for i in range(s+1):
    if i*2 >= s:
        ans -= dp1[i]*3 + mod*3
        ans %= mod
    if i*2 == s:
        ans += dp2[i]*3
        ans %= mod

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_sum = sum(a)
half = int(a_sum / 2)

dp = [[0] * (a_sum + 1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(n):
    ni = i+1
    for j in range(a_sum+1):
        if dp[i][j] != 0:
            dp[ni][j] += (dp[i][j] * 2) % MOD
            dp[ni][j+a[i]] += dp[i][j]
ans = pow(3, n, MOD)
for item in dp[n][half:]:
    ans -= item * 3
    ans %= MOD

if a_sum % 2 == 0:
    dp = [[0] * (half + 1) for _ in range(n+1)]
    dp[0][0] = 1
    for i in range(n):
        ni = i+1
        for j in range(half):
            dp[ni][j] += dp[i][j] % MOD
            if j+a[i] < half+1:
                dp[ni][j+a[i]] += dp[i][j] % MOD
ans += dp[n][half] * 3
ans %= MOD
if ans < 0:
    ans += MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

a_list = []
for _ in range(N):
    a = int(input())
    a_list.append(a)

import itertools

sum_edge = sum(a_list)

ans = 0
for i in range(1, len(a_list)-2+1):
    for comb in itertools.combinations(a_list,i):
        #print(comb)
        max_edge = sum(comb)
        if max_edge > sum_edge-max_edge:
            ans += 1 * 6
MAGIC_NUMBER = 998244353
print(ans % MAGIC_NUMBER)

Submission status: Wrong Answer

Solution code:
N = int(input())

a_list = []
for _ in range(N):
    a = int(input())
    a_list.append(a)

    
import itertools

sum_edge = sum(a_list)

ans = 0
for i in range(1, len(a_list)-2+1):
    for comb in itertools.combinations(a_list,i):
        #print(comb)
        max_edge = sum(comb)
        if max_edge > sum_edge-max_edge:
            ans += 1 * 6
print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 998244353
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a_sum = sum(a)
half = int(a_sum / 2)

dp = [[0] * (a_sum + 1) for _ in range(n+1)]
dp[0][0] = 1
for i, item in enumerate(a):
    ni = i+1
    for j in range(a_sum+1):
        if dp[i][j] != 0:
            dp[ni][j] += (dp[i][j] * 2) % MOD
            dp[ni][j+item] += dp[i][j]
ans = pow(3, n, MOD) - (sum(dp[n][half:])*3)

if a_sum % 2 == 0:
    dp = [[0] * (half + 1) for _ in range(n+1)]
    dp[0][0] = 1
    for i, item in enumerate(a):
        ni = i+1
        for j in range(half):
            dp[ni][j] += dp[i][j] % MOD
            if j+item < half+1:
                dp[ni][j+item] += dp[i][j] % MOD
ans += dp[n][half] * 3
ans %= MOD
if ans < 0:
    ans += MOD
print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())

a_list = []
for _ in range(N):
    a = int(input())
    a_list.append(a)

    
def dfs(i, a_list, r_list, g_list, b_list):
    if len(a_list) == i:
        if len(r_list)==0 or len(g_list)==0 or len(b_list)==0:
            return 0
        r = sum(r_list)
        g = sum(g_list)
        b = sum(b_list)
        max_edge = max(r, g, b)
        if max_edge > r+b+g-max_edge:
            return 0
        else:
            return 1
    
    r = dfs(i+1, a_list, r_list[:]+[a_list[i]], g_list[:], b_list[:])
    g = dfs(i+1, a_list, r_list[:], g_list[:]+[a_list[i]], b_list[:])
    b = dfs(i+1, a_list, r_list[:], g_list[:], b_list[:]+[a_list[i]])
    return r+g+b

MAGIC_NUMBER = 998244353
ans = dfs(0, a_list, [], [], [])
print(ans % MAGIC_NUMBER)

Submission status: Wrong Answer

Solution code:

n = int( input() )

an = [0]*n

for i in range(n):
    an[i] = int(input())



an.sort()
def f(index, r, g, b):

    if n < index :
        return 0


    mmm = sorted([r,g,b]) 
    if mmm[2] >= mmm[1] + mmm[0]:
        return 0

    if index == n :
        return 1
        

    v = an[index]
    
    t = 0
    t += f(index + 1, r + v, g    , b ) 
    t += f(index + 1, r    , g + v, b ) 
    t += f(index + 1, r    , g    , b + v ) 

    return t

v = an[0]
ans =  f(1,v,0,0)
ans += f(1,0,v,0)
ans += f(1,0,0,v)

mod = 998244353
print(ans % mod )

Submission status: Wrong Answer

Solution code:
from sys import stdin
N = int(stdin.readline().rstrip())
ans = stdin.readline().rstrip()
sum = 0
left = 0
right = 0
for itr in range(0,len(ans)):
    count_dot = 0
    count_sharp = 0
    left = itr
    right = left + 1
    if left == len(ans)-1:
        break
    if ans[left] == '#' and ans[right] == '.':
        while(right < N and ans[right] == '.'):
            count_dot += 1
            right += 1
        while(left >= 0 and ans[left] == '#'):
            count_sharp += 1
            left -= 1
        # print(count_dot, count_sharp)
        sum += min(count_dot, count_sharp)
print(sum)

Submission status: Wrong Answer

Solution code:
#出来たとこまで
import itertools
import math

n = int(input())
alist = [int(input()) for i in range(n)]
a_sum = sum(alist)

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    
def f():
     ans = 0
     for i in range(n):
          for j in list(itertools.combinations(alist, i+1)):
               j_sum = sum(j)
               if (a_sum-1)//2 >= j_sum and j_sum >= (a_sum-1)//3+1:
                    blist = []
                    for k in alist:
                         if k not in j:
                              blist.append(k)
                    for l in range(len(blist)):
                         for m in list(itertools.combinations(blist,l+1)):
                              c = a_sum-j_sum-sum(m)
                              if sum(m)>=1 and sum(m)<=j_sum:
                                   c = a_sum-j_sum-sum(m)
                                   if c>=1 and c<=j_sum:
                                        ans += 1
     return (ans*6)%998244353

print(f())