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:
n = int(input())
a = [int(input()) for i in range(n)]
mod = 998244353
sm = sum(a)
dp = [[0 for i in range(sm+1)] for j in range(n+1)]
dp2 = [[0 for i in range(sm+1)] for j in range(n+1)]
dp[0][0] = 1
dp2[0][0] = 1
for i in range(1,n+1):
  x = a[i-1]
  dp2[i] = dp2[i-1][:]
  for j in range(sm+1):
      dp[i][j] = dp[i-1][j]*2
      if j >= x:
        dp[i][j] += dp[i-1][j-x]
        dp2[i][j] += dp2[i-1][j-x]
      dp[i][j] %= mod
      dp2[i][j] %= mod
ans = pow(3,n,mod)-sum(dp[-1][(sm+1)//2:])*3
if sm%2:
  print(ans%mod)
else:
  print((ans+dp2[-1][sm//2]//2*6)%mod)

Submission status: Wrong Answer

Solution code:
N = int(input())
P = 998244353
K, s, t, b = 400, 1, 1, 0
for _ in range(N):
    a = int(input())
    b += a
    s *= (1<<a*K) + 2
    t *= (1<<a*K) + 1

ans = 0
for i in range((b+1)//2, b+1):
    ans += s >> K*i & (2**K-1)
if b % 2 == 0: ans -= (t>>K*b//2 & (2**K-1))
print((3**N - ans*3) % P)

Submission status: Wrong Answer

Solution code:
mod=998244353 

N=int(input())
alist=[]
for i in range(N):
  alist.append(int(input()))
  
asum=sum(alist)
#print(alist)

dp=[]
for _ in range(N+1):
  dp.append([0]*(asum+1))
  
dp[0][0]=1
#print(dp)
for i in range(N):
  a=alist[i]
  for j in range(asum):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    if dp[i][j] > 0:
      dp[i+1][j+a] += dp[i][j]
      dp[i+1][j+a] %= mod
    
#print(dp)
invalid_num = 0
for i in range((asum+1)//2,asum+1):
  invalid_num += dp[N][i]
  invalid_num %= mod
  
#print(invalid_num)
if asum%2 == 0:
  print((3**N-3*invalid_num+dp[N][asum//2]//3)%mod)
else:
  print((3**N-3*invalid_num)%mod)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import ceil

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

modulo = 998244353

a.sort(reverse=True)
cumsump1 = 1
s = sum(a)

dp = np.zeros(s + 1, dtype=np.int32)
dp[0] = 1
for ai in a:
    cumsump1 += ai
    dp[ai:cumsump1] = 2 * dp[ai:cumsump1] + dp[: -ai + cumsump1]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo

ans = 3 ** n % modulo
ans -= 3 * dp[ceil(s / 2) :].sum()

if s % 2 == 0:
    dp = np.zeros(s // 2 + 1, dtype=np.int32)
    dp[0] = 1
    for ai in a:
        dp[ai:] = (dp[ai:] + dp[:-ai]) % modulo

    ans += 3 * dp[s // 2]

ans %= modulo

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.uint32)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]
    dp %= modulo
sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()


if s % 2 == 0:
    dp = np.zeros(s // 2 + 1, dtype=np.uint32)
    dp[0] = 1
    for ai in a:
        dp[ai:] = (dp[ai:] + dp[:-ai]) % modulo

    sol += 3 * dp[s // 2]

sol %= modulo

print(sol)

Submission status: Wrong Answer

Solution code:
import numpy as np
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = 2 * dp[ai:] + dp[:-ai]
    dp[:ai] = 2 * dp[:ai]

sol = 3 ** n % modulo
sol -= 3 * dp[ceil(s / 2) :].sum()


if s % 2 == 0:
    dp = np.zeros(s + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] = dp[ai:] + dp[:-ai]

    sol += 3 * dp[s // 2]
sol %= modulo

print(sol)

Submission status: Wrong Answer

Solution code:
import numpy as np

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = np.zeros(s + 1, dtype=np.int)
dp[0] = 1
for ai in a:
    dp[ai:] = dp[ai:] * 2 + dp[:-ai]
    dp[:ai] *= 2

sol = 3 ** n % modulo
sol -= 3 * dp[(s + 1) // 2 :].sum()
sol %= modulo

if s % 2 == 0:
    dp = np.zeros(s + 1, dtype=np.int)
    dp[0] = 1
    for ai in a:
        dp[ai:] += dp[:-ai]

    sol += 3 * dp[s // 2]
    sol %= modulo

print(sol)

Submission status: Wrong Answer

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

a_sum = sum(A)
total = 3 ** N
# Rが最大の辺
dp = [[0 for _ in range(a_sum + 1)] for _ in range(N + 1)]
# dp[現在の辺番号][Rの辺の長さ]
dp[0][0] = 1

for i, a in enumerate(A):
    for n in range(a_sum + 1 - a):
        # dp[i][n] -> dp[i][n+a]
        dp[i + 1][n + a] += dp[i][n]
        dp[i + 1][n] += dp[i][n] * 2

dp2 = [[0 for _ in range(a_sum + 1)] for _ in range(N + 1)]
# dp[現在の辺番号][Rの辺の長さ]
dp2[0][0] = 1

for i, a in enumerate(A):
    for n in range(a_sum + 1 - a):
        dp2[i + 1][n] += dp2[i][n]
        dp2[i + 1][n + a] += dp2[i][n]

ans = total
for i in range(a_sum + 1):
    if i >= a_sum - i:
        ans -= dp[N][i] * 3
    if i == a_sum - i:
        ans += dp2[N][i] * 3

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2),dtype = np.int32)
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],1] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,:-k,1]
	dp[i,:,1] += dp[i-1,:,1]
	if(i%10 == 0):
		dp[i,:,:] = dp[i,:,:]%DIV
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(suma % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))

Submission status: Wrong Answer

Solution code:
import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2))
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],1] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,:-k,1]
	dp[i,:,1] += dp[i-1,:,1]
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(suma % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))

Submission status: Wrong Answer

Solution code:
import numpy as np

DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)

dp = np.zeros((N,suma+1,2))
dp[0,0,0] = 2
dp[0,a[0],0] = 1
dp[0,0,1] = 1
dp[0,a[0],0] = 1

allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	dp[i,k:,0] += dp[i-1,:-k,0]
	dp[i,:,0] += dp[i-1,:,0]*2
	dp[i,k:,1] += dp[i-1,-k,1]
	dp[i,:,1] += dp[i-1,:,1]
allc = allc - sum(dp[N-1,suma-suma/2:,0])*3
if(N % 2 == 0):			
	allc += dp[N-1,suma/2,1]*3
print(int(allc%DIV))

Submission status: Wrong Answer

Solution code:
import math
import copy
import numpy as np

MOD = 998244353

n = int(input())
xxs = []
total = 0
for _ in range(n):
    t = int(input())
    xxs.append(t)
    total += t

xs = np.array(xxs)
dp = np.array([[0] * (total+1) for _ in range(n)])

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): # length of
    s = xs[i]
    curtotal += s
    dp[i] = (dp[i-1] * 2)
    dp[i][s:] += dp[i-1][:-s]
    dp[i] %= MOD

#print(dp)

plus = 0
if total % 2 == 0:
    dp2 = np.array([0] * (total // 2 + 1))
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        dp2[s:] += dp2[:-s]
        dp2 %= MOD
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)

Submission status: Wrong Answer

Solution code:
import math
import copy
import numpy as np

MOD = 998244353

n = int(input())
xxs = []
total = 0
for _ in range(n):
    t = int(input())
    xxs.append(t)
    total += t

xs = np.array(xxs)
dp = np.array([[0] * (total+1) for _ in range(n)])

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): # length of
    s = xs[i]
    curtotal += s
    dp[i] = (dp[i-1] * 2)
    dp[i][s:] += dp[i-1][:-s]
    dp[i] %= MOD

#print(dp)

plus = 0
if total % 2 == 0:
    dp2 = np.array([0] * (total // 2 + 1))
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        dp2[s:] += dp2[:-s]
        dp2 %= MOD
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)

Submission status: Wrong Answer

Solution code:
import math
import copy

MOD = 998244353

n = int(input())
xs = []
total = 0
for _ in range(n):
    t = int(input())
    xs.append(t)
    total += t

dp = [[0] * (total+1) for _ in range(n)]

dp[0][0] = 2
dp[0][xs[0]] = 1
'''
for i in range(1,n): # length of
    s = xs[i]
    for j in range (0,total+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j - s >= 0:
            dp[i][j] = (dp[i][j] + dp[i-1][j-s]) % MOD
'''
plus = 0
if total % 2 == 0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    intotal = 0
    for i in range(n):
        s = xs[i]
        prev = copy.copy(dp2)
        for j in range(0,len(dp2)):
            if j-s >= 0:
                dp2[j] =  (dp2[j] + prev[j-s]) % MOD
                #print(i,j,s,dp2)
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)

Submission status: Wrong Answer

Solution code:
import math
import copy

n = int(input())
xs = []
total = 0
for _ in range(n):
    t = int(input())
    xs.append(t)
    total += t

dp = [[0] * (total+1) for _ in range(n)]

dp[0][0] = 2
dp[0][xs[0]] = 1

for i in range(1,n): # length of
    s = xs[i]
    for j in range (0,total+1):
        dp[i][j] = dp[i-1][j] * 2
        if j - s >= 0:
            dp[i][j] += dp[i-1][j-s]

plus = 0
if total % 2 == 0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    intotal = 0
    for i in range(n):
        s = xs[i]
        prev = copy.copy(dp2)
        for j in range(0,len(dp2)):
            if j-s >= 0:
                dp2[j] =  dp2[j] + prev[j-s]
                #print(i,j,s,dp2)
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus += dp[n-1][i]

#print(3**n, minus, plus)
print(3**n - minus*3 + plus*3)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict
def input():
	return sys.stdin.readline()[:-1]
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
dp = [defaultdict(int) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
	for j in range(i, -1, -1):
		for k, v in dp[j].items():
			dp[j+1][k+a[i]] += v

#print(dp)
res = 0
for i in range(1, n+1):
	for k, v in dp[i].items():
		if k*2 >= s:
			res += 3 * pow(2, n-i, MOD) * v
			res %= MOD
print((pow(3, n, MOD) - res) % MOD)

Submission status: Wrong Answer

Solution code:
def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

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

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

    # dp
    sum_now = A[0]
    for i in range(1, N):
        a = A[i]
        sum_now += a
        for length in range(0, sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= a:
                dp[i][length] = dp[i - 1][length - a] + dp[i - 1][length] << 1
            else:
                dp[i][length] = dp[i-1][length] << 1
            dp[i][length] %= mod

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = dp2[i - 1][length - a] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def dp_table(*counts):  # dp[x][y]を作りたかったら dp_table(xのサイズ,yのサイズ)
    if counts:
        return [dp_table(*counts[1:]) for _ in range(counts[0])]
    else:
        return 0


def main():

    N = int(input())
    A = [int(input()) for i in range(N)]
    mod = 998244353
    ans = pow(3, N, mod)
    sum_A = sum(A)
    dp = dp_table(N, sum_A + 1)
    # dp[i][j]: i番目までの中から辺をいくつか選んで、長さがjになるパターン数

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

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

    # dp
    sum_now = A[0]
    for i in range(1, N):
        sum_now += A[i]
        for length in range(0, sum_now+1):
            # A[i]を追加しないのなら他の２食のうちどちらに入れるかで2倍選択肢がある
            if length >= A[i]:
                dp[i][length] = dp[i - 1][length - A[i]] + dp[i - 1][length] * 2
            else:
                dp[i][length] = dp[i-1][length]*2
            dp[i][length] %= mod
        for length in range(min(sum_now, sum_A//2+1)):
            if length >= A[i]:
                dp2[i][length] = dp2[i - 1][length - A[i]] + dp2[i - 1][length]
            else:
                dp2[i][length] = dp2[i-1][length]
            dp2[i][length] %= mod
    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: 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] = dp[:m] * 2 % 998244353

border = (total + 1) // 2
yo = sum(dp[border:]) % 998244353 * 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]) % 998244353
    yo = yo - dp2[-1] * 3 % 998244353

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

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] = dp[:m] * 2 % 998244353

border = (total + 1) // 2
yo = sum(dp[border:]) % 998244353 * 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])% 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 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(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

# dp=[[0 for _ in range(ASum+1)] for _ in range(2)]
dp=np.zeros((2,ASum+1),dtype=np.int64)
dp[0][0] = 2
dp[0][A[0]] = 1

# dpOther=[[0 for _ in range(ASum+1)] for _ in range(2)]
dpOther=np.zeros((2,ASum+1),dtype=np.int64)
dpOther[0][0] = 1
dpOther[0][A[0]] = 1

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

	if ASum %2 == 0:
		dpOther[current,:] = dpOther[prev,:] % MOD
		dpOther[current,a:] = dpOther[prev,:-a] % 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:
from functools import lru_cache

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

MOD = 998244353
S = sum(a)

# 全パターン
ans = 1
for _ in range(N):
    ans *= 3
    ans %= MOD

# Rが2/S以上となるもの * 3 を引く
@lru_cache(maxsize=None)
def dp(i, s):
    if i==0:
        if s==0:
            return 2
        elif s==a[0]:
            return 1
        else:
            return 0
    return (2*dp(i-1, s) + (dp(i-1, s-a[i]) if s-a[i] >=0 else 0)) % MOD

ans -= 3 * sum(dp(N-1, s) for s in range((S+1)//2, S+1)) % MOD
if ans < 0:
    ans += MOD

# R==G==2/S
@lru_cache(maxsize=None)
def dp(i, s):
    if i==0:
        if s==0:
            return 1
        elif s==a[0]:
            return 1
        else:
            return 0
    return (dp(i-1, s) + (dp(i-1, s-a[i]) if s-a[i] >=0 else 0)) % MOD

if S&1==0:
    ans += 3 * dp(N-1, S/2) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
Q = 998244353
N = int( input())
A = [ int( input()) for _ in range(N)]
S = sum(A)
H = (S+1)//2
dp = [0]*(S+1)
dp[0] = 1
for a in A:
    for s in range(S, a-1, -1):
        dp[s] = (dp[s]*2 + dp[s-a])%Q
    for s in range(a-1,-1,-1):
        dp[s] = dp[s]*2%Q
ans = (pow(3, N, Q) - sum(dp[H:])%Q*3%Q)%Q
if S%2 == 0:
    dp = [0]*(S+1)
    dp[0] = 1
    for a in A:
        for s in range(S,a-1,-1):
            dp[s] = (dp[s] + dp[s-a])%Q
    ans += dp[H]*3
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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


def func():
    ab = np.zeros(m1, dtype='int32')
    ab[m] = 1
    for i in range(N):
        c = a[i]
        ab[:-c] = (2 * ab[:-c] + ab[c:]) % 998244353
        ab[-c:] = (2 * ab[-c:] + ab[m]) % 998244353
    return ab[0]


def func1():
    ab = np.zeros(m1, dtype='int32')
    ab[m] = 1
    for i in range(N):
        c = a[i]
        ab[:-c] = (ab[:-c] + ab[c:]) % 998244353
        ab[-c:] = ab[-c:]
    return ab[0]


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 21 18:51:07 2019

@author: Yamazaki Kenichi
"""

N = int(input())
A = [int(input()) for i in range(N)]
mod = 998244353
def mof(x):
    return x % mod
total = sum(A)
dp1 = [[0 for i in range(300*N+1)] for i in range(N+1)]
dp2 = [[0 for i in range(300*N+1)] for i in range(N+1)]
dp1[0][0], dp2[0][0] = 1,1
for i in range(N):
    for j in range(N*300+1):
        dp1[i+1][j] = mof(dp1[i][j]*2 + (dp1[i][j-A[i]] if j >= A[i] else 0))
        dp2[i+1][j] = mof(dp2[i][j] + (dp2[i][j-A[i]] if j >= A[i] else 0))
        
ex = mof(sum(dp1[N][(total+1)//2:]))
a = dp2[N][total//2] if total % 2 == 0 else 0

ans = mof(3**N - 3*ex + 2*a)
print(ans)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[int(input()) for i in range(N)]
a.sort(reverse=True)
su=sum(a)
#すべての組み合わせのリストと可能な三角形の集合を作り、前者の要素のうち後者にある物の数を返す。

bool_list=[]
A,B,C=0,0,0

#i項目を選んだかどうかで再帰する関数
def saiki(i,A,B,C):
    if judge(A,B,C)!=True:
        return
    if i==N:
        bool_list.append(True)
        return
    suuchi=a[i]
    saiki(i+1,A+suuchi,B,C)
    saiki(i+1,A,B+suuchi,C)
    saiki(i+1,A,B,C+suuchi)

#与えられた3つの数について三角不等式を満たすかboolを返す

def judge(n,m,l):
    if n>=su:
        return False
    if m>=su:
        return False
    if l>=su:
        return False
    return True

saiki(0,A,B,C)

print(bool_list.count(True)%998244353)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[int(input()) for i in range(N)]
a.sort()
su=sum(a)
#すべての組み合わせのリストと可能な三角形の集合を作り、前者の要素のうち後者にある物の数を返す。

bool_list=[]
A,B,C=0,0,0

#i項目を選んだかどうかで再帰する関数
def saiki(i,A,B,C):
    if judge(A,B,C)!=True:
        return
    if i==N:
        bool_list.append(True)
        return
    suuchi=a[i]
    saiki(i+1,A+suuchi,B,C)
    saiki(i+1,A,B+suuchi,C)
    saiki(i+1,A,B,C+suuchi)

#与えられた3つの数について三角不等式を満たすかboolを返す

def judge(n,m,l):
    if n>=su:
        return False
    if m>=su:
        return False
    if l>=su:
        return False
    return True

saiki(0,A,B,C)

print(bool_list.count(True)%998244353)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[int(input()) for i in range(N)]
su=sum(a)
#すべての組み合わせのリストと可能な三角形の集合を作り、前者の要素のうち後者にある物の数を返す。

bool_list=[]
A,B,C=0,0,0

#i項目を選んだかどうかで再帰する関数
def saiki(i,A,B,C):
    if judge(A,B,C)!=True:
        return
    if i==N:
        bool_list.append(True)
        return
    suuchi=a[i]
    saiki(i+1,A+suuchi,B,C)
    saiki(i+1,A,B+suuchi,C)
    saiki(i+1,A,B,C+suuchi)

#与えられた3つの数について三角不等式を満たすかboolを返す

def judge(n,m,l):
    if n>=su:
        return False
    if m>=su:
        return False
    if l>=su:
        return False
    return True

saiki(0,A,B,C)

print(bool_list.count(True)%998244353)

Submission status: Wrong Answer

Solution code:
N=int(input())
a=[int(input()) for i in range(N)]
#すべての組み合わせのリストと可能な三角形の集合を作り、前者の要素のうち後者にある物の数を返す。

bool_list=[]
A,B,C=0,0,0

#i項目を選んだかどうかで再帰する関数
def saiki(i,A,B,C):
    if judge(A,B,C)!=True:
        return 
    if i==N:
        bool_list.append(True)
        return
    suuchi=a[i]
    saiki(i+1,A+suuchi,B,C)
    saiki(i+1,A,B+suuchi,C)
    saiki(i+1,A,B,C+suuchi)

#与えられた3つの数について三角不等式を満たすかboolを返す

def judge(n,m,l):
    if n>=m+l:
        return False
    if m>=n+l:
        return False
    if l>=m+n:
        return False
    return True

saiki(0,A,B,C)

print(bool_list.count(True)%998244353)

Submission status: Wrong Answer

Solution code:
M,z,s=998244353,1,0
N,*A=map(int,open(0))
d=[1]+[0]*7**6
e=[1]+[0]*7**6
for a in A:
 i=s;s+=a;z*=3
 while~i:d[i+a]+=d[i]%M;d[i]*=2;e[i+a]+=e[i]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
print(z+~s%2*e[s//2]*3%M)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
N = int(input())
A = [int(input()) for i in range(N)]
S = sum(A)
MOD = 998244353

ans = pow(3,N,MOD)

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

suma = 0
for i,a in enumerate(A):
    for j in range(suma + 1):
        dp[i+1][j] += dp[i][j]*2
        dp[i+1][j] %= MOD
        dp[i+1][j+a] += dp[i][j]
        dp[i+1][j+a] %= MOD
    suma += a

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

if S%2==0:
    tmp = dp[-1][S//2]//3
    ans += tmp
    ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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


def func():
    ab = np.zeros((N + 1, m1), dtype='int64')
    ab[0, m] = 1
    for i in range(N):
        c = a[i]
        ab[i + 1, :-c] = (2 * ab[i, :-c] + ab[i, c:]) % 998244353
        ab[i + 1, -c:] = (2 * ab[i, -c:] + ab[i, m]) % 998244353
    return ab[N, 0]


def func1():
    ab = np.zeros((N + 1, m1), dtype='int64')
    ab[0, m] = 1
    for i in range(N):
        c = a[i]
        ab[i + 1, :-c] = ab[i, :-c] + ab[i, c:]
        ab[i + 1, -c:] = ab[i, -c:]
    return ab[N, 0]


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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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


def func():
    ab = np.zeros((N + 1, m1), dtype='int64')
    ab[0, m] = 1
    for i in range(N):
        c = a[i]
        ab[i + 1, :-c] = (2 * ab[i, :-c] + ab[i, c:]) % 998244353
        ab[i + 1, -c:] = (2 * ab[i, -c:] + ab[i, m]) % 998244353
    return ab[N, 0]


def func1():
    ab = np.zeros((N + 1, m1), dtype='int64')
    ab[0, m] = 1
    for i in range(N):
        c = a[i]
        ab[i + 1, :-c] = ab[i, :-c] + ab[i, c:]
        ab[i + 1, -c:] = ab[i, -c:]
    return ab[N, 0]


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

Submission status: Wrong Answer

Solution code:
import numpy as np

mod = 998244353


def sum_mod(v):
    ans = 0
    for i in range(1, len(v)):
        ans = (ans + v[i]) % mod
    return ans


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

dp = np.zeros((n + 1, A + 1), dtype=int)
dp2 = np.zeros((n + 1, A + 1), dtype=int)
dp[0][0] = 1
dp2[0][0] = 1
for t in range(1, n + 1):
    dp[t, :] = dp[t - 1, :] * 2 % mod
    dp2[t, :] = dp2[t - 1, :] % mod
    dp[t, a[t - 1]:] += dp[t - 1, :-a[t - 1]] % mod
    dp2[t, a[t - 1]:] += dp2[t - 1, :-a[t - 1]] % mod
#print(dp)

ans = 3 ** n % mod
ans -= np.sum(dp[n][(A + 1) // 2:]) * 3 % mod
if A % 2 == 0:
    ans += dp2[n][A // 2] * 3 % mod
print(ans)

Submission status: Wrong Answer

Solution code:
def ceil(a: int, b: int)->int:
    if a//b * b == a:
        return a//b
    return a//b + 1


def pow_mod(a: int, n: int, mod: int)->int:
    ''' (a^n) % mod
    '''
    if n == 0:
        return 1
    if n % 2:
        t = pow_mod(a, n-1, mod)
        return (a * t) % mod
    # if n % 2 == 0:
    t = pow_mod(a, n >> 1, mod)
    return (t * t) % mod


def three_colors(N: int, A: list)->int:
    MOD = 998244353

    S = sum(A)
    limit = ceil(S, 2)
    Rbiggest = [[0] * (limit+1) for _ in range(N+1)]
    Rbiggest[0][0] = 1

    # R が S/2 以上になる場合を計数する
    for i, a in enumerate(A):
        for r in range(limit+1):
            # R を使わない場合。
            # B/G の二通りあるので 2 をかける
            Rbiggest[i+1][r] = (Rbiggest[i+1][r] + 2*Rbiggest[i][r]) % MOD

            if limit <= r + a:
                # limit 以上はまとめる
                Rbiggest[i+1][limit] = \
                    (Rbiggest[i+1][limit] + Rbiggest[i][r]) % MOD
            else:
                # それ以外は普通に計上する
                Rbiggest[i+1][r+a] = \
                    (Rbiggest[i+1][r+a] + Rbiggest[i][r]) % MOD

    if S % 2 > 0:
        # S が奇数の場合は R=G=S/2,B=0 あるいは R=B=S/2,G=0
        # となることがないので、それらの重複を考える必要はない。
        return (pow_mod(3, N, MOD) - 3*Rbiggest[N][limit]) % MOD

    # R=G=S/2,B=0 あるいは R=B=S/2,G=0 の重複を補正するために
    # これらの数を数えたい。今回は、R=B=S/2 の場合だけ数える。
    ReqG = [[0] * (limit+1) for _ in range(N+1)]
    ReqG[0][0] = 1
    for i, a in enumerate(A):
        for r in range(limit+1):
            # R を使わない場合。
            # 今回は使わないものは全部 G に突っ込むので x1
            ReqG[i+1][r] = (ReqG[i+1][r] + 1*ReqG[i][r]) % MOD

            if r + a <= limit:
                # 今回は limit 以上になるものは全て破棄
                ReqG[i+1][r+a] = (ReqG[i+1][r] + ReqG[i][r]) % MOD

    return (pow_mod(3, N, MOD) - 3*Rbiggest[N][limit] + 3*ReqG[N][limit]) % MOD


if __name__ == "__main__":
    N = int(input())
    A = [int(input()) for _ in range(N)]

    ans = three_colors(N, A)
    print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)
# import time

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


MOD = 998244353

N = d_in()
total = 3 ** N - (2**N - 2) * 3 - 3

a_list = []
for _ in range(N):
    a_list.append(d_in())
sum_a = sum(a_list)

# 1要素目: i番目の整数までを考慮
# 2要素目: [both>0, 緑>0&青==0, 緑==0&青>0, both==0]
# 3要素目: 最大の色(赤とする)の和
dp = np.zeros((N+1, 3, 1 + (sum_a+1)//2), dtype=int)
dp[0, 2, 0] = 1

for i in range(1, N+1):
    # 赤に入れる
    a = a_list[i-1]
    dp[i, :, a:] += dp[i-1, :, :-a]
    dp[i, :, -1] += dp[i-1, :, -a:].sum(axis=1)

    # 緑or青に入れる
    dp[i, 0, :] += (dp[i-1, 0, :] + dp[i-1, 1, :]) * 2
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 2, :]

    if i % 15 == 0:
        dp[i, :, :] %= MOD

dp %= MOD
print((total - dp[-1, 0, -1].sum() * 3) % MOD)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import bisect
MOD = 998244353
n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
a.sort(reverse=True)
a_sum = sum(a)
half = int(sum(a) / 2)

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

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

Submission status: Wrong Answer

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

sum_A = sum(A)
MOD = 998244353

dp1 = [0] * (sum_A + 1)
dp2 = [0] * (sum_A + 1)
dp1[0] = dp2[0] = 1
tmp_sum = 0

for a in A:
    for i in reversed(range(tmp_sum + 1)):
        dp1[i] %= MOD
        dp2[i] %= MOD
        # R に塗れる場合
        dp1[i + a] += dp1[i]
        dp1[i] <<= 1
        dp2[i + a] += dp2[i]
        dp2[i] <<= 1
    tmp_sum += a


ans = pow(3, N, MOD)
for i in range(sum_A + 1):
    if i * 2 >= sum_A:
        ans = (ans - dp1[i] * 3 + MOD * 3) % MOD
    if i * 2 == sum_A:
        ans = (ans + dp2[i] * 3) % MOD
print(ans)