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: Runtime Error

Solution code:
import sys
import math
import numpy as np


MOD=998244353
N=int(input())
a=[int(input()) for i in range(N)]
a.sort(reverse=True)

A=sum(a)
M=math.ceil(A/2)  
x =[ [0 for j in range(M+1)] for i in range(N)]
x[0][0]=2
x[0][min(a[0],M)]=1

p=M-A+a[0]
q=a[0]
for i in range(1,N):
    p+=a[i]
    q+=a[i]
    for j in range(max(p,0),min(q,M)+1):
        if j==M:
            x[i][j]=sum(x[i-1][ max(M-a[i],0): M ])+x[i-1][M]*3

        elif j-a[i]<0: x[i][j]=x[i-1][j]*2
        else: x[i][j]=x[i-1][j]*2+x[i-1][j-a[i]]

        x[i][j]%=MOD

if sum(a)%2==0:
    y =[ [0 for j in range(M+1)] for i in range(N)]
    y[0][0]=1
    p=M-A+a[0]
    q=a[0]
    for i in range(1,N):
        p+=a[i]
        q+=a[i]
        for j in range(max(p,0),min(q,M)+1):
            if j-a[i]<0: y[i][j]=y[i-1][j]
            else: y[i][j]=y[i-1][j]+y[i-1][j-a[i]]

            y[i][j]%=MOD

    ans=3**N-x[N-1][M]*3+y[N-1][M]*6



else: ans=3**N-x[N-1][M]*3
print(ans%MOD)

Submission status: Runtime Error

Solution code:
from operator import mul
from functools import reduce
def comb2(n,r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under
def comb3(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M, K = LI()

cou = int(0)
#maxL = N + M -2
L = int(0)
#距離i+1の組み合わせ

#for i in range(maxL):
for j in range(N):
    L += (N - j - 1) * (M ** 2) * (j + 1)
for j in range(M):
    L += (M - j - 1) * (N ** 2) * (j + 1)
#    for j in range(i+2):
#        if i>1 and i+1>j>0:
#            L[i] += max((N-j)*(M-(1+i)+j),0)*(i+1)*2
#        else:
#            L[i] += max(((N - j) * (M - (1 + i) + j)), 0) * (i + 1)

cou = comb2(N*M-2,K-2)*L%mod

print(cou)

Submission status: Runtime Error

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

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

sumA = sum(a)

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

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

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

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

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

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

Submission status: Runtime Error

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

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

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

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

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

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

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

Submission status: Runtime Error

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

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

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

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

INF = 1<<29

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

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

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


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

DIV = 998244353

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

def main():
    dp1 = [0]*(SUM+1)
    dp3 = [0]*(SUM+1)
    dp1[0]=1
    dp3[0]=1
    
    for n in range(N):
        a = As[n]
        dp1 = [(dp1[s]+(dp1[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]
        dp3 = [(dp3[s]*2 + (dp3[s-a] if s>=a else 0))%DIV for s in range(SUM+1)]

    S3 = (sum(dp3[(SUM+1)//2:])*3)%DIV
    S1 = (dp1[(SUM)//2]*3)%DIV if SUM%2==0 else 0
    return (ALL - S3 + S1 + DIV) % DIV

print(main())

Submission status: Runtime Error

Solution code:
iimport 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]
  memotmpe = memoe[i-1]
  memotmp = np.concatenate((np.zeros((a[i-1]), dtype=np.int), memotmp),axis=1)
  memotmpe = np.concatenate((np.zeros((a[i-1]), dtype=np.int), memotmpe),axis=1)
  memo[i] = (memo[i-1]*2 + memotmp[:suma+1])%mod
  memoe[i] = (memoe[i-1] + memotmpe[: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: Runtime Error

Solution code:
N = int(input())
a = [int(input()) for _ in range(N)]
mod = 998244353
suma = sum(a)
memo = [[0]*(suma+1) for _ in range(N+1)]
memo[0][0] = 1
memoe = [[0]*(suma+1) for _ in range(N+1)]
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 = [0]*a[i-1] + memotmp
  for j in range(sum(a[:i])+1):
    memo[i][j] = (memo[i-1][j]*2 + memotmp[j])%mod
    memoe[i][j] = (memoe[i-1][j] + memotmp[j])%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: Runtime Error

Solution code:
N = int(input())
a = [int(input()) for _ in range(N)]
mod = 998244353
suma = sum(a)
memo = [[0]*(suma+1) for _ in range(N+1)]
memo[0][0] = 1
memoe = [[0]*(suma+1) for _ in range(N+1)]
memoe[0][0] = 1

ttl = 3
for i in range(N-1):
  ttl *=3
  ttl %= mod
  
for i in range(N+1):
  for j in range(suma+1):
    if i==0:
      continue
    elif j - a[i-1]<0:
      memo[i][j]=(memo[i-1][j]*2)%mod
      memoe[i][j]=(memoe[i-1][j])%mod
    else:
      memo[i][j]=(memo[i-1][j]*2+memo[i-1][j-a[i-1]])%mod
      memoe[i][j]=(memoe[i-1][j]+memoe[i-1][j-a[i-1]])%mod

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

Submission status: Runtime Error

Solution code:
def main():
	N = int(input())
	A = [0]*N
	for i in range(N):
		A[i] = int(input())
 
	memo = dict()
	def create_triangles(r, g, b, num):
		ans = 0
		if num == N:
			if (abs(b-g)<r and r<b+g) or (abs(b-r)<g and g<b+r) or (abs(r-g)<b and b<r+g):
				return 1
			else:
				return 0
		if not (r+A[num],g,b) in memo:
			tmp = create_triangles(r+A[num], g, b, num+1)
			memo[(r+A[num],g,b)] = tmp
			memo[(r+A[num],b,g)] = tmp
			memo[(b,r+A[num],g)] = tmp
			memo[(b,g,r+A[num])] = tmp
			memo[(g,r+A[num],b)] = tmp
			memo[(g,b,r+A[num])] = tmp
		ans += memo[(r+A[num],g,b)]
		ans %= 998244353
 
		if not (r,g+A[num],b) in memo:
			tmp = create_triangles(r, g+A[num], b, num+1)
			memo[(r,g+A[num],b)] = tmp
			memo[(r,b,g+A[num])] = tmp
			memo[(b,r,g+A[num])] = tmp
			memo[(b,g+A[num],r)] = tmp
			memo[(g+A[num],r,b)] = tmp
			memo[(g+A[num],b,r)] = tmp
		ans += memo[(r,g+A[num],b)]
		ans %= 998244353
 
		if not (r,g,b+A[num]) in memo:
			tmp = create_triangles(r, g, b+A[num], num+1)
			memo[(r,g,b+A[num])] = tmp
			memo[(r,b+A[num],g)] = tmp
			memo[(b+A[num],r,g)] = tmp
			memo[(b+A[num],g,r)] = tmp
			memo[(g,r,b+A[num])] = tmp
			memo[(g,b+A[num],r)] = tmp
		ans += memo[(r,g,b+A[num])]
		ans %= 998244353
 
		return ans
 
	ans = create_triangles(0,0,0,0)
	print(ans)
 
 
if __name__ == '__main__':
    main()
def main():
	N = int(input())
	A = [0]*N
	for i in range(N):
		A[i] = int(input())

	memo = dict()
	def create_triangles(r, g, b, num):
		ans = 0
		if num == N:
			if (abs(b-g)<r and r<b+g) or (abs(b-r)<g and g<b+r) or (abs(r-g)<b and b<r+g):
				return 1
			else:
				return 0
		if not (r+A[num],g,b) in memo:
			tmp = create_triangles(r+A[num], g, b, num+1)
			memo[(r+A[num],g,b)] = tmp
			memo[(r+A[num],b,g)] = tmp
			memo[(b,r+A[num],g)] = tmp
			memo[(b,g,r+A[num])] = tmp
			memo[(g,r+A[num],b)] = tmp
			memo[(g,b,r+A[num])] = tmp
		ans += memo[(r+A[num],g,b)]
		ans %= 998244353

		if not (r,g+A[num],b) in memo:
			tmp = create_triangles(r, g+A[num], b, num+1)
			memo[(r,g+A[num],b)] = tmp
			memo[(r,b,g+A[num])] = tmp
			memo[(b,r,g+A[num])] = tmp
			memo[(b,g+A[num],r)] = tmp
			memo[(g+A[num],r,b)] = tmp
			memo[(g+A[num],b,r)] = tmp
		ans += memo[(r,g+A[num],b)]
		ans %= 998244353

		if not (r,g,b+A[num]) in memo:
			tmp = create_triangles(r, g, b+A[num], num+1)
			memo[(r,g,b+A[num])] = tmp
			memo[(r,b+A[num],g)] = tmp
			memo[(b+A[num],r,g)] = tmp
			memo[(b+A[num],g,r)] = tmp
			memo[(g,r,b+A[num])] = tmp
			memo[(g,b+A[num],r)] = tmp
		ans += memo[(r,g,b+A[num])]
		ans %= 998244353

		return ans

	ans = create_triangles(0,0,0,0)
	print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
a = np.array([int(input()) for _ in range(N)])
m = 998244353
S = a.sum()

# 最初のt個の整数を塗り分け, Rの整数の和がrであるような場合の数
DP_A = np.zeros((N+1, S+1), dtype=np.int64)
# 最初のt個の整数を塗り分け, Rの整数の和がrで, Bの和が0であるような場合の数
DP_B = np.zeros((N+1, S+1), dtype=np.int64)

DP_A[0, 0] = 1
DP_B[0, 0] = 1

for t in range(N):
    for r in range(S + 1):
        # t + 1番目の整数をRにしない -> G or Bにする
        DP_A[t+1, r] = DP_A[t, r] * 2 % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_A[t+1, r] += DP_A[t, r - a[t]] % m
        # t+1 番目の整数をRにしない -> Gを加える
        DP_B[t+1, r] = DP_B[t, r] % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_B[t+1, r] += DP_B[t, r - a[t]] % m


res1 = DP_A[N, int(np.ceil(S/2)):].sum()
res2 = DP_B[N, int(np.ceil(S/2))] if S % 2 == 0 else 0
res = (3 ** N - res1 * 3 + res2 * 3) % m
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
a = np.array([int(input()) for _ in range(N)])
m = 998244353
S = a.sum()

# 最初のt個の整数を塗り分け, Rの整数の和がrであるような場合の数
DP_A = np.zeros((N+1, S+1), dtype=np.int64)
# 最初のt個の整数を塗り分け, Rの整数の和がrで, Bの和が0であるような場合の数
DP_B = np.zeros((N+1, S+1), dtype=np.int64)

DP_A[0, 0] = 1
DP_B[0, 0] = 1

# for t in range(N):
#     for r in range(S + 1):
#         # t + 1番目の整数をRにしない -> G or Bにする
#         DP_A[t+1, r] = DP_A[t, r] * 2 % m
#         # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
#         if r - a[t] >= 0:
#             DP_A[t+1, r] += DP_A[t, r - a[t]] % m
#         # t+1 番目の整数をRにしない -> Gを加える
#         DP_B[t+1, r] = DP_B[t, r] % m
#         # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
#         if r - a[t] >= 0:
#             DP_B[t+1, r] += DP_B[t, r - a[t]] % m

for t in range(N):
    DP_A[t+1, :] = (DP_A[t, :]) * 2 % m
    DP_A[t+1, a[t]:] += DP_A[t, :-a[t]] % m
    DP_B[t+1, :] = (DP_B[t, :]) % m
    DP_B[t+1, a[t]:] += DP_B[t, :-a[t]] % m

res1 = DP_A[N, int(np.ceil(S/2)):].sum()
res2 = DP_B[N, int(np.ceil(S/2))] if S % 2 == 0 else 0
res = (3 ** N - res1 * 3 + res2 * 3) % m
print(res)

Submission status: Runtime Error

Solution code:
N = int(input())
a = np.array([int(input()) for _ in range(N)])
m = 998244353
S = a.sum()

# 最初のt個の整数を塗り分け, Rの整数の和がrであるような場合の数
DP_A = np.zeros((N+1, S+1), dtype=np.int64)
# 最初のt個の整数を塗り分け, Rの整数の和がrで, Bの和が0であるような場合の数
DP_B = np.zeros((N+1, S+1), dtype=np.int64)

DP_A[0, 0] = 1
DP_B[0, 0] = 1

for t in range(N):
    for r in range(S + 1):
        # t + 1番目の整数をRにしない -> G or Bにする
        DP_A[t+1, r] = DP_A[t, r] * 2 % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_A[t+1, r] += DP_A[t, r - a[t]] % m
        # t+1 番目の整数をRにしない -> Gを加える
        DP_B[t+1, r] = DP_B[t, r] % m
        # t + 1番目の整数をRにする -> r-a(t+1)だった場合の数を追加
        if r - a[t] >= 0:
            DP_B[t+1, r] += DP_B[t, r - a[t]] % m

res1 = DP_A[N, int(np.ceil(S/2)):].sum()
res2 = DP_B[N, int(np.ceil(S/2))] if S % 2 == 0 else 0
res = (3 ** N - res1 * 3 + res2 * 3) % m
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np

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

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.uint32)
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.uint32)
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: Runtime Error

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)
dp1[0,0] = 1
dp2 = np.zeros(N+1, s//2+1)
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: Runtime Error

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

n = int(input())
s = list(input())
res = 10**6
ctw = 0
ctb = 0
w = [0]*n
b = [0]*n

for i in range(n):
     if s[i] == ".":
          ctw += 1
     else:
          ctb += 1
     w[i]= ctw
     b[i]= ctb
for i in range(n):
     res = min(res,b[i]+w[-1]-w[i])
res = min(res,w[-1],b[-1])
print(res)

Submission status: Runtime Error

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 % 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: Runtime Error

Solution code:
import sys

def way(moku, wa, cur):
    if wa==moku:
        return 1
    if cur == n or wa > moku:
        return 0
    re1 = way(moku, wa + ms[cur], cur + 1)
    re2 = way(moku, wa, cur + 1)
    return re1 + re2

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

total=sum(ms)
dp=[0]*(total+1)
dp[0]=1
for m in ms:
    for i in range(total,m-1,-1):
        dp[i]=dp[i]*2+dp[i-m]
    for i in range(m):
        dp[i]*=2
    print(m,dp)

border = (total + 1) // 2
yo=sum(dp[border:])*3
if total%2==0:
    yo-=way(total//2,0,0)*3
print((3**n-yo)%998244353)

Submission status: Runtime Error

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

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = 0
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = 0
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    memo1[i][c] = acc
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Submission status: Runtime Error

Solution code:
import sys

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

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = max(0, memo0[i][c])
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = max(0, memo1[i][c])
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Submission status: Runtime Error

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

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret = (ret * 3) % 998244353

memo0 = [[-1] * 100000 for _ in range(300)]
def dfs0(i, c):
    if 0 <= memo0[i][c]:
        return memo0[i][c]

    if i == len(aa):
        memo0[i][c] = 3 if total <= (2 * c) else 0
        return memo0[i][c]

    acc = max(0, memo0[i][c])
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c)) % 998244353
    acc = (acc + dfs0(i + 1, c + aa[i])) % 998244353
    memo0[i][c] = acc
    return memo0[i][c]

memo1 = [[-1] * 100000 for _ in range(300)]
def dfs1(i, c):
    if 0 <= memo1[i][c]:
        return memo1[i][c]

    if i == len(aa):
        memo1[i][c] = 3 if total == (2 * c) else 0
        return memo1[i][c]

    acc = max(0, memo1[i][c])
    acc = (acc + dfs1(i + 1, c)) % 998244353
    acc = (acc + dfs1(i + 1, c + aa[i])) % 998244353
    return memo1[i][c]

ret = (ret - dfs0(0, 0)) % 998244353
ret = (ret + dfs1(0, 0)) % 998244353
print(ret)

Submission status: Runtime Error

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

MOD =998244353
def solve(N,a):
    sum_a = sum(a)
    dp = [[0 for _ in range(sum_a+1)] for _ in range(N+1)]
    dp[0][0] = 1
    for j in range(1,N+1):
        dp[j][0] = (2 * dp[j-1][0])%MOD

    for i in range(1,N+1):
        for j in range(1,sum_a+1):
            if j-a[i-1]>=0:
                dp[i][j] = ( dp[i][j] + dp[i-1][j]*2 +dp[i-1][j-a[i-1]])%MOD
            else:
                dp[i][j] = ( dp[i][j] + dp[i-1][j]*2 )%MOD
    all_combination = 1
    for i in range(N):
        all_combination = (all_combination*3) %MOD
    half_sum_a = sum_a //2 if sum_a %2 == 0 else sum_a//2+1 
    bigger_than_half = sum(dp[N][half_sum_a:])
    if sum_a %2 == 0:
        half_dp = [[0 for _ in range(sum_a+1)] for _ in range(N+1)]
        half_dp[:,0] = 1
        for i in range(1,N+1):
            for j in range(1,sum_a+1):
                if j-a[i-1]>=0:
                    half_dp[i][j] = ( half_dp[i][j] + half_dp[i-1][j] +half_dp[i-1][j-a[i-1]])%MOD
                else:
                    half_dp[i][j] = ( half_dp[i][j] + half_dp[i-1][j] )%MOD
        half_half = half_dp[N][half_sum_a]
        
    else:
        half_half = 0
    return int(all_combination - 3* bigger_than_half + 3* half_half)%MOD

    
if __name__ =="__main__":
    N,a = get_input()
    ans = solve(N,a)
    print(ans)

Submission status: Runtime Error

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

MOD =998244353
def solve(N,a):
    sum_a = sum(a)
    dp = [[0 for _ in range(sum_a+1)] for _ in range(N+1)]
    dp[0][0] = 1
    for j in range(1,N+1):
        dp[j][0] = (2 * dp[j-1][0])%MOD

    for i in range(1,N+1):
        for j in range(1,sum_a+1):
            if j-a[i-1]>=0:
                dp[i][j] = ( dp[i][j] + dp[i-1][j]*2 +dp[i-1][j-a[i-1]])%MOD
            else:
                dp[i][j] = ( dp[i][j] + dp[i-1][j]*2 )%MOD
    all_combination = 1
    for i in range(N):
        all_combination = (all_combination*3) %MOD
    half_sum_a = sum_a //2 if sum_a %2 == 0 else sum_a//2+1 
    bigger_than_half = sum(dp[N][half_sum_a:])
    if sum_a %2 == 0:
        halfdp = [[0 for _ in range(sum_a+1)] for _ in range(N+1)]
        half_dp[:,0] = 1
        for i in range(1,N+1):
            for j in range(1,sum_a+1):
                if j-a[i-1]>=0:
                    half_dp[i][j] = ( half_dp[i][j] + half_dp[i-1][j] +half_dp[i-1][j-a[i-1]])%MOD
                else:
                    half_dp[i][j] = ( half_dp[i][j] + half_dp[i-1][j] )%MOD
        half_half = half_dp[N][half_sum_a]
        
    else:
        half_half = 0
    return int(all_combination - 3* bigger_than_half + 3* half_half)%MOD

    
if __name__ =="__main__":
    N,a = get_input()
    ans = solve(N,a)
    print(ans)

Submission status: Runtime Error

Solution code:
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):
    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]
total = 1
for i in range(n):
    total *= 3
    total = total % MOD
ans = total - (sum(dp[n][half:])*3)

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

Submission status: Runtime Error

Solution code:
from itertools import combinations

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

indices = set(range(len(A)))
A_length = len(A)

count = 0
for a_n in range(1, A_length-1):
    for a_t in combinations(indices, a_n):
        for b_n in range(1, A_length-a_n):
            for b_t in combinations(indices-set(a_t), b_n):
                for c_t in combinations(indices-set(a_t)-set(b_t), A_len-a_n-b_n):
                    a = sum([A[i] for i in a_t])
                    b = sum([A[i] for i in b_t])
                    c = sum([A[i] for i in c_t])
                    if (a+b)>c and (b+c)>a and (c+a)>b:
                        count += 1

print(count)

Submission status: Runtime Error

Solution code:
from itertools import permutations

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

indices = set(range(len(A)))
A_length = len(A)

count = 0
for a_n in range(1, A_length-1):
    for a_t in combinations(indices, a_n):
        for b_n in range(1, A_length-a_n):
            for b_t in combinations(indices-set(a_t), b_n):
                for c_t in combinations(indices-set(a_t)-set(b_t), A_len-a_n-b_n):
                    a = sum([A[i] for i in a_t])
                    b = sum([A[i] for i in b_t])
                    c = sum([A[i] for i in c_t])
                    if (a+b)>c and (b+c)>a and (c+a)>b:
                        count += 1

print(count)

Submission status: Runtime Error

Solution code:
#3secかかってよいし、全探索できる。
N = int(input())
Numbers = []
for i in range(N):
    Numbers.append(int(input()))
#Numbersのどのインデックスが赤に塗られてどれが緑に塗られどれが青に塗られているかを調べる。

R = 0
G = 0
B = 0
index = 0
cnt = 0

def searchConbinationColors(index):
    global Numbers
    global cnt
    global R
    global G
    global B
    if index == N:
        rsum = sum(R)
        gsum = sum(G)
        bsum = sum(B)
        if rsum + gsum =< bsum or gsum + bsum <= rsum or bsum + rsum <= gsum:
            return
        else:
            cnt += 1
            return
    nindex += index
    R.append(Numbers[index])
    searchConbinationColors(nindex)
    R.pop()
    G.append(Numbers[index])
    searchConbinationColors(nindex)
    G.pop()
    B.append(Numbers[index])
    searchConbinationColors(nindex)
    B.pop()
    return

searchConbinationColors(0)

print(cnt)

Submission status: Runtime Error

Solution code:
from math import factorial
n=int(input())
a=[]
for i in range(n+1):
    a.append(int(input()))
a.sort()
sum_a=sum(a)
la=[]
tmp=0
for i in range(n):
    tmp+=a[i]
    la.append(tmp)
    if tmp>sum_a/2:
        d=i
        break
ans=0
nk1=n-(k+1)
for i in range(nk1):
    ans+=2**(k+1+i)*(factorial(nk1) / factorial(i+1) / factorial(nk1 - (i+1))
)
l=[]
for i in range(nk1):
    for j in la:
        if j>a[k+1+i]:
            l.append(j)
            break
ans=0
nk1=n-(k+1)
for i in range(nk1):
    ans+=2**(k+1+i)*(factorial(nk1) / factorial(i+1) / factorial(nk1 - (i+1))
)*l[i+1]

print(ans%998244353)

Submission status: Runtime Error

Solution code:
N=int(input())
S=input()
sl=[x for x in S]
sh=0
p=0
for i in range(N-1):
    if sl[i]=='#':
        sh+=1
    if sl[-i-1]=='.':
        p+=1

cnt=N-p-sh
print(p)

Submission status: Runtime Error

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

total = 0
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        ret = 1 if c < a + b else 0
        memo[(a, b, c)] = ret
        return ret
    if total < (2 * c)
        memo[(a, b, c)] = 0
        return 0
    if (a, b, c) in memo:
        return memo[(a, b, c)]

    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)] = ret
    return ret

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

Submission status: Runtime Error

Solution code:
import sys

import numpy as np

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

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

#memo = {}


def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
#    if (a, b, c, i) in memo:
#        return memo[(a, b, c, i)]

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

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

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

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


ret = dfs(0, 0, 0, 0)
print(ret)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

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

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
    if (a,b,c,i) in memo:
        return memo[(a,b,c,i)]

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

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

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


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

ret = dfs(0, 0, 0, 0)
print(ret)

Submission status: Runtime Error

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 = [readInt() for _ in range(n)]

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
    if (a,b,c,i) in memo:
        return memo[(a,b,c,i)]

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

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

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


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

ret = dfs(0, 0, 0, 0)
print(ret)