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 _ in range(N)]

cum = [0]
for i in range(N):
  cum.append(cum[-1]+A[i])

dp = [[0]*(cum[-1]+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(1,N+1):
  for j in range(cum[i]+1):
    dp[i][j] = dp[i-1][j] + dp[i-1][j-A[i-1]]*2
    print(i,j)
    
print(dp)

Submission status: Wrong Answer

Solution code:
from numpy import zeros, roll

mod = 998244353

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

S = sum(A)

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

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

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

M = (S + 1) // 2

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

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


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

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

ans = 3*sum(dp[N][i] for i in range((s+1)//2,s+1))
ans %= mod
if s % 2 == 0:
    ans -= dp[N][s//2]

a = pow(3,N,mod)

print((a-ans) % mod)

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    import numpy as np
    n = int(input())
    a = sorted([int(input()) for _ in [0]*n])
    dp = np.array([1], dtype=np.int64)
    DP = np.array([1], dtype=np.int64)
    s = 1
    mod = 998244353
    for i in a:
        dp2 = np.concatenate([dp, np.zeros(i, dtype=np.int64)])
        DP2 = np.concatenate([dp, np.zeros(i, dtype=np.int64)])
        dp2[i:] = (dp2[i:]+2*dp) % mod
        DP2[i:] = (DP2[i:]+2*DP) % mod
        dp = dp2
        DP = DP2
        s += i
    ALL = sum(dp)
    A = sum(dp[(s-1)//2+1:])
    if s % 2 == 1:
        B = DP[s//2]
    else:
        B = 0
    print((3*A-2*ALL+3*B) % mod)


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
from collections import deque
import itertools
from copy import deepcopy
import random
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_pow(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod_>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:return num
def get_primes(n,type="int"):
    if n==0:
        if type=="int":return []
        else:return [False]
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=1):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=""):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
    return ret
def seifu(x):
    return x//abs(x)
######################################################################################################
def main():
    n=int(input())
    md=998244353

    A=[]
    for a in range(n):
        A.append(int(input()))
    dp=[[0 for b in range(sum(A)+1)] for a in range(n+1)]
    dp[0][0]=1
    ssum=sum(A)
    for a in range(1,n+1):
        for b in range(0,ssum+1):
            dp[a][b]=dp[a-1][b]*2+(dp[a-1][b-A[a-1]] if b-A[a-1]>=0 else 0)
    ans=sum(dp[-1][1:ssum//2])
    ans%=md
    print(ans)
main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 998244353
inf = 1e10

#solve
def solve():
    n = II()
    ans = pow(3, n, mod)
    p = [pow(2, i, mod) for i in range(n + 1)]
    a = IR(n)
    a.sort()
    acc = list(itertools.accumulate(a))
    dp = [[0] * (acc[-1] + 1) for i in range(n + 1)]
    dp[0][0] = 1
    for i, ai in enumerate(a):
        for j in range(i + 1, 0, -1):
            for k in range(acc[i], ai - 1, -1):
                dp[j][k] += dp[j - 1][k - ai]
                dp[j][k] %= mod

    for i in range(1, n + 1):
        for j in range((acc[-1] - 1) // 2 + 1, acc[-1] + 1):
            ans -= dp[i][j] * p[n - i] * 3
            ans %= mod
    print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

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

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

main()

Submission status: Wrong Answer

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

MOD = 998244353

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

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

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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 998244353

def main():
    n, *a = map(int, sys.stdin.read().split())
    S = sum(a)
    dp = [[0 for _ in range(S+1)] for _ in range(n+1)]
    dp[0][0] = 1
    
    for i in range(n):
        for r in range(S+1):
            if r >= a[i]:
                dp[i+1][r] = (dp[i][r-a[i]] + dp[i][r] * 2) % MOD
            else:
                dp[i+1][r] = dp[i][r] * 2 % MOD

    # if S % 2 == 0:
    #     ans = (pow(3, n, MOD) - ((sum(dp[n][S//2+1:]) * 3) % MOD)) % MOD
    # else:
    #     ans = (pow(3, n, MOD) - (sum(dp[n][S//2+1:]) * 3 % MOD)) % MOD
    # print(ans)
    m = 1
    for _ in range(n):
        m = m * 3 % MOD # overflow 対策

    ans = (m - (sum(dp[n][S//2+1:]) * 3 % MOD)) % MOD
    # Sが奇数だったらこれでいい 偶数だったらさらに、(dp[n][S//2]を３倍して、そこから(R = G = S/2, B = 0) となる場合の数を２倍して引いた通り数) を引けばいい
    # if S % 2 == 0:
    #     ans = (ans - (dp[n][S//2] * 3 - (dp[n][S//2] - dp[n][0]) * 3)) % MOD
    
    # print(dp[n])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 998244353

def main():
    n, *a = map(int, sys.stdin.read().split())
    S = sum(a)
    dp = [[0 for _ in range(S+1)] for _ in range(n+1)]
    dp[0][0] = 1
    
    for i in range(n):
        for r in range(S+1):
            dp[i+1][r] += dp[i][r] * 2
            if r >= a[i]:
                dp[i+1][r] += dp[i][r-a[i]]

            dp[i+1][r] %= MOD

    # if S % 2 == 0:
    #     ans = (pow(3, n, MOD) - ((sum(dp[n][S//2+1:]) * 3) % MOD)) % MOD
    # else:
    #     ans = (pow(3, n, MOD) - (sum(dp[n][S//2+1:]) * 3 % MOD)) % MOD
    # print(ans)
    ans = (pow(3, n, MOD) - ((sum(dp[n][S//2+1:]) * 3) % MOD)) % MOD
    # Sが奇数だったらこれでいい 偶数だったらさらに、(dp[n][S//2]を３倍して、そこから(R = G = S/2, B = 0) となる場合の数を２倍して引いた通り数) を引けばいい
    if S % 2 == 0:
        ans = (ans - (dp[n][S//2] * 3 - (dp[n][S//2] - dp[n][0]) * 3)) % MOD
        
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

sumA = sum(a)

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

sumA = sum(a)

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

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

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

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

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

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

Submission status: Wrong Answer

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

from copy import deepcopy




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp.copy()
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    ans = pow(3, num, mod) - dp[(1 + sum_num) // 2:].sum() * 3
    if sum_num % 2 == 0:
        dp2 = np.zeros(sum_num + 1, dtype=np.int64)
        dp2[0] = 1
        for i in range(num):
            now_num = data[i]
            prev = deepcopy(dp2)
            # dp2 = 1 * prev
            dp2[now_num:] = prev[:-now_num]
            dp2 %= mod
        ans += dp2[sum_num // 2] * 3


    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp.copy()
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    ans = pow(3, num, mod) - dp[(1 + sum_num) // 2:].sum() * 3
    if sum_num % 2 == 0:
        dp2 = np.zeros(sum_num + 1, dtype=np.int64)
        dp2[0] = 1
        for i in range(num):
            now_num = data[i]
            prev = dp2.copy()
            # dp2 = 1 * prev
            dp2[now_num:] = prev[:-now_num]
            dp2 %= mod
        ans += dp2[sum_num // 2] * 3


    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    ans = pow(3, num, mod) - dp[(1 + sum_num) // 2:].sum() * 3
    if sum_num % 2 == 0:
        dp2 = np.zeros(sum_num + 1, dtype=np.int64)
        dp2[0] = 1
        for i in range(num):
            now_num = data[i]
            prev = dp2
            dp2 = 1 * prev
            dp2[now_num:] = prev[:-now_num]
            dp2 %= mod
        ans += dp2[sum_num // 2] * 3


    ans %= mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    ans = pow(3, num, mod) - dp[(1 + sum_num) // 2:].sum() * 3
    if sum_num % 2 == 0:
        dp2 = np.zeros(sum_num + 1, dtype=np.int64)
        dp2[0] = 1
        for i in range(num):
            now_num = data[i]
            prev = dp2
            dp2[now_num:] += prev[:-now_num]
            dp2 %= mod
        # hikukazu -= dp2[sum_num // 2]
        ans += dp2[sum_num // 2] * 3




    # hikukazu = 0
    # for i in range(math.ceil(sum_num / 2), sum_num + 1):
    #     hikukazu += dp[i]

    # ans -= hikukazu * 3
    ans %= mod
    print(ans)
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    dp2 = np.zeros(sum_num + 1, dtype=np.int64)
    dp2[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp2
        dp2 = prev
        dp2[now_num:] += prev[:-now_num]
        dp2 %= mod

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    dp2 = np.zeros(sum_num + 1, dtype=np.int64)
    dp2[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp2
        dp2[now_num:] += prev[:-now_num]
        dp2 %= mod

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

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




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    dp2 = np.zeros(sum_num + 1, dtype=np.int64)
    dp2[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp2
        dp2[now_num:] += prev[:-now_num]
        dp2 %= mod

    ans = pow(3, num, mod)
    hikukazu = 0
    for i in range((1 + sum_num) // 2, sum_num + 1):
        hikukazu += dp[i]
    if sum_num % 2 == 0:
        hikukazu -= dp2[sum_num // 2]
    ans -= hikukazu * 3
    ans %= mod
    print(ans)
    # print(dp)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

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




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

    dp = np.zeros(sum_num + 1, dtype=np.int64)
    dp[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp
        dp = 2 * prev
        dp[now_num:] += prev[:-now_num]
        dp %= mod

    dp2 = np.zeros(sum_num + 1, dtype=np.int64)
    dp2[0] = 1
    for i in range(num):
        now_num = data[i]
        prev = dp2
        dp2[now_num:] += prev[:-now_num]
        dp2 %= mod

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

sys.setrecursionlimit(1000000)
mod = 1000000007

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

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

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

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

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

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

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

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

Submission status: 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:
        dp[a:] += dp[:-a]
        dp %= MOD
    answer += dp[S//2] * 3
answer %= MOD
print(answer)