Problem:


Score : 600 points

Problem Statement

You are given N integers. The i-th integer is a_i.
Find the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the following condition is satisfied:

Let R, G and B be the sums of the integers painted red, green and blue, respectively. There exists a triangle with positive area whose sides have lengths R, G and B.

Constraints

3 \leq N \leq 300

1 \leq a_i \leq 300(1\leq i\leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1
:
a_N

Output

Print the number, modulo 998244353, of ways to paint each of the integers red, green or blue so that the condition is satisfied.

Sample Input 1

4
1
1
1
2

Sample Output 1

18

We can only paint the integers so that the lengths of the sides of the triangle will be 1, 2 and 2, and there are 18 such ways.

Sample Input 2

6
1
3
2
3
5
2

Sample Output 2

150

Sample Input 3

20
3
1
4
1
5
9
2
6
5
3
5
8
9
7
9
3
2
3
8
4

Sample Output 3

563038556



Sample input:
4
1
1
1
2


Sample output:
18

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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 i==N:
        bool_list.append(judge(A,B,C))
        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: Time Limit Exceeded

Solution code:
N = int(input())
a = [int(input()) for _ in range(N)]
s = sum(a)
m = (s + 1) // 2
m1 = m + 1

ab = [[-1] * m1 for _ in range(N + 1)]
for j in range(m):
    ab[N][j] = 0
ab[N][m] = 1
for j in range(N - 1, 0, -1):
    ab[j][m] = (3 * ab[j + 1][m]) % 998244353


def func(n, r):
    if r >= m:
        return ab[n][m]
    else:
        if ab[n][r] > -1:
            return ab[n][r]
        else:
            ret = (func(n + 1, r + a[n]) + 2 * func(n + 1, r)) % 998244353
            ab[n][r] = ret
            return ret


def func1(n, r):
    if n == N - 1:
        if r + a[n] == m:
            return 1
        else:
            return 0
    elif r + a[n] > m:
        return func1(n + 1, r)
    elif r + a[n] == m:
        return 1 + func1(n + 1, r)
    else:
        return (func1(n + 1, r + a[n]) + func1(n + 1, r)) % 998244353


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

print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
M=998244353
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
for _ in range(input()):
	a=input();s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print z%M

Submission status: Time Limit Exceeded

Solution code:
M=998244353
d=[0]*90301
d[0]=1
e=[0]*90301
e[0]=1
z=1
s=0
exec'''a=input();s+=a;i=s;z*=3
while~i:d[i]+=d[i]+d[i-a]%M;e[i]+=e[i-a]%M;i-=1
'''*input()
i=s
while i*2>=s:z=(z-d[i]*3)%M;i-=1
z+=~s%2*e[s//2]*3
print z%M

Submission status: Time Limit Exceeded

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

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

ab = [[-1] * m1 for _ in range(N)]
ab.append([0] * m1)
ab[N][m] = 1
for j in range(N -1, 0, -1):
    ab[j][m] = (3 * ab[j + 1][m]) % 998244353


def func(n, r):
    if r >= m:
        return ab[n][m]
    else:
        if ab[n][r] > -1:
            return ab[n][r]
        else:
            ret = (func(n + 1, r + a[n]) + 2 * func(n + 1, r)) % 998244353
            ab[n][r] = ret
            return ret


def func1(n, r):
    if n == N - 1:
        if r + a[n] == m:
            return 1
        else:
            return 0
    elif r + a[n] > m:
        return func1(n + 1, r)
    elif r + a[n] == m:
        return 1 + func1(n + 1, r)
    else:
        return (func1(n + 1, r + a[n]) + func1(n + 1, r)) % 998244353


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

print(ans % 998244353)

Submission status: Time Limit Exceeded

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

M = 998244353

S = sum(A)
dp = [0 for _ in range(S + 1)]
dp[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = (2 * dp[i] + dp[i - a]) % M
    for i in range(a - 1, -1, -1):
        dp[i] = (2 * dp[i]) % M
dp2 = [0 for _ in range(S + 1)]
dp2[0] = 1
for a in A:
    for i in range(S, a - 1, -1):
        dp2[i] = (dp2[i] + dp2[i - a]) % M
s = 0
for i in range((S + 1) // 2, S + 1):
    s = (s + dp[i]) % M
ans = (3**N - 3 * s) % M
if S % 2 == 0:
    ans = (3**N - 3 * s + 3 * dp2[S // 2]) % M
print(ans)

Submission status: Time Limit Exceeded

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

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


def func():
    ab = [[0] * m1 for _ in range(N + 1)]
    ab[0][m] = 1
    for i in range(N):
        c = a[i]
        for j in range(m1 - c):
            ab[i + 1][j] = (2 * ab[i][j] + ab[i][j + c]) % 998244353
        for j in range(m1 - c, m1):
            ab[i + 1][j] = (2 * ab[i][j] + ab[i][m]) % 998244353
    return ab[N][0]


def func1():
    ab = [[0] * m1 for _ in range(N + 1)]
    ab[0][m] = 1
    for i in range(N):
        c = a[i]
        for j in range(m1 - c):
            ab[i + 1][j] = (ab[i][j] + ab[i][j + c]) % 998244353
        for j in range(m1 - c, m1):
            ab[i + 1][j] = ab[i][j]
    return ab[N][0]


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

Submission status: Time Limit Exceeded

Solution code:
M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]
		d[i+a]%=M
		d[i]*=2
		d[i]%=M
		e[i+a]+=e[i]
		e[i+a]%=M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])

Submission status: Time Limit Exceeded

Solution code:
M=998244353
N=int(input())
d=[0]*90001
d[0]=1
e=[0]*90001
e[0]=1
z=1
s=0
for _ in range(N):
	a=int(input())
	i=s
	while i>=0:
		d[i+a]+=d[i]%M
		d[i]*=2
		e[i+a]+=e[i]%M
		i-=1
	s+=a
	z=z*3%M
for i in range(s+1>>1,s+1):
	z-=d[i]*3
	z%=M
print([(z+e[s//2]*3)%M,z][s%2])

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=[int(input()) for i in range(N)]
mod=998244353
def add(a,b):
    return (a+b)%mod
def sub(a,b):
    return (a-b)%mod
def mul(a,b):
    return ((a%mod)*(b%mod))%mod
def pow(x,y):
    if y==0:
        return 1
    elif y==1:
        return x%mod
    elif y%2==0:
        return pow(x,y//2)**2 % mod
    else:
        return pow(x,y//2)**2 * x % mod
def div(a,b):
    return mul(a,pow(b,mod-2))

sum_S=sum(S)
dp=[[0]*(sum_S+1) for i in range(N)]
dp2=[[0]*(sum_S//2+1) for i in range(N)]

dp[0][0]=2
dp[0][S[0]]=1
dp2[0][0]=1
dp2[0][S[0]]=1
for i in range(1,N):
    for j in range(sum_S+1):
        dp[i][j]=mul(dp[i-1][j],2)
        if j-S[i]>=0 and dp[i-1][j-S[i]]!=0:
            dp[i][j]=add(dp[i][j],dp[i-1][j-S[i]])

        if j<=sum_S//2:
            dp2[i][j]=dp2[i-1][j]
            if j-S[i]>=0 and dp2[i-1][j-S[i]]!=0:
                dp2[i][j]=add(dp2[i][j],dp2[i-1][j-S[i]])

if sum_S%2==0:
    print((pow(3,N)-sum(dp[N-1][sum_S//2:])*3+dp2[N-1][-1]*3)%mod)
else:
    print((pow(3,N)-sum(dp[N-1][sum_S//2+1:])*3)%mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353


def pow(a, b):
    ans = 1
    for i in range(b):
        ans = ((ans % mod) * (a % mod)) % mod
    return ans


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 = [[0 for _ in range(A+1)] for _ in range(n+1)]
dp2 = [[0 for _ in range(A+1)] for _ in range(n+1)]
dp[0][0] = 1
dp2[0][0] = 1
for t in range(1, n+1):
    for r in range(0, A+1):
        dp[t][r] = dp[t-1][r] * 2 % mod
        dp2[t][r] = dp2[t-1][r] % mod
        if r - a[t-1] >= 0:
            dp[t][r] = (dp[t][r] + dp[t-1][r-a[t-1]]) % mod
            dp2[t][r] = (dp2[t][r] + dp2[t-1][r-a[t-1]]) % mod
# print(dp)

ans = pow(3, n)
for r in range((A + 1) // 2, A+1):
    ans -= dp[n][r] * 3
    ans %= mod
    ans += mod
    ans %= mod
if A % 2 == 0:
    ans = (ans + dp2[n][A // 2] * 3) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

dp = [ [0] * (SUM + 1) for _ in range(N+1) ]
dp2 = [ [0] * (SUM + 1) for _ in range(N+1) ]
# red [i][r] : rまで塗った
dp[0][0] = 1
dp2[0][0] = 1
for i in range(N):
    a = A[i]
    for r in range(0, SUM-a +1):
        #pick
        dp[i+1][r+a] = ( dp[i+1][r+a] + dp[i][r] ) % MOD
        dp2[i+1][r+a] = ( dp2[i+1][r+a] + dp2[i][r] ) % MOD


    for r in range(0, SUM + 1):
        # nopick    
        # B,G に入れる 2通り考える
        dp[i+1][r] = (dp[i+1][r] +  dp[i][r] * 2 ) % MOD
        dp2[i+1][r] = (dp2[i+1][r] +  dp2[i][r]  ) % MOD

if SUM % 2 ==0:
    notans = sum(dp[N][ SUM//2 : ]) * 3 % MOD

    notans = ( notans - 3 * dp2[N][SUM//2] ) %MOD
    cand = pow(3, N, MOD)

    print(  (cand - notans + MOD) % MOD  )
else:
    notans = sum(dp[N][ SUM//2 + 1: ]) * 3 % MOD
    cand = pow(3, N, MOD)
    print(  (cand - notans + MOD) % MOD  )

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def num_sum(n: int, a: list, dp: list, mod):
    dp[0][0] = 1
    nodes = [(0,0)]
    for i in range(n):
        next_nodes = set()
        for r,sm in nodes:
            next_nodes.add((r,sm))
            next_nodes.add((r+1, sm+a[i]))
            
            dp[r+1][sm+a[i]] += dp[r][sm]
            dp[r+1][sm+a[i]] %= mod
            
        nodes = sorted(list(next_nodes), key=lambda x: x[1], reverse=True)
    return dp

def remove(n: int, a: list, dp: list, mod):
    ret = 0
    thr = sum(a)/2
    for r in range(1,n-1):
        for sm in range(sum(a)+1):
            if sm < thr:
                continue
            
            ret += dp[r][sm] * 3*((pow(2,n-r,mod) - 2)%mod)
            ret %= mod
            
    return ret

n = ni()
a = [ni() for _ in range(n)]
dp = [[0]*(sum(a)+1) for _ in range(n+1)]
mod = 998244353

dp = num_sum(n,a,dp,mod)

ans = pow(3, n, mod) - 3*pow(2, n, mod) + 3 - remove(n,a,dp,mod)

print(ans % mod)

Submission status: Time Limit Exceeded

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 > 0:
        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+a] + 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: Time Limit Exceeded

Solution code:
N = int(input())

total = 0
A = []
for i in range(N):
    a = int(input())
    total += a
    A.append(a)

mod = 998244353

dp = [[0]*91000 for i in range(N+1)]
dp[0][0] = 1
for i in range(1, N+1):
    for j in range(300*i, -1, -1):
        dp[i][j+A[i-1]] += dp[i-1][j]
        dp[i][j+A[i-1]] %= mod
        dp[i][j] += 2*dp[i-1][j]
        dp[i][j] %= mod

exc = 0
for j in range((total+1)//2, total+1):
    exc += dp[N][j]
    exc %= mod

res = (3**N % mod) - exc * 3

if total % 2 == 0:
    dp = [[0]*91000 for i in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        for j in range(300*i, -1, -1):
            dp[i][j+A[i-1]] += dp[i-1][j]
            dp[i][j+A[i-1]] %= mod
            dp[i][j] += dp[i-1][j]
            dp[i][j] %= mod
    res += dp[N][total//2] * 3

print(res % mod)

Submission status: Time Limit Exceeded

Solution code:
san=[1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907, 43046721, 129140163, 387420489, 164017114, 492051342, 477909673, 435484666, 308209645, 924628935, 777398099, 335705591, 8872420, 26617260, 79851780, 239555340, 718666020, 159509354, 478528062, 437339833, 313775146, 941325438, 827487608, 485974118, 459678001, 380789650, 144124597, 432373791, 298877020, 896631060, 693404474, 83724716, 251174148, 753522444, 264078626, 792235878, 380218928, 142412431, 427237293, 283467526, 850402578, 554719028, 665912731, 1249487, 3748461, 11245383, 33736149, 101208447, 303625341, 910876023, 736139363, 211929383, 635788149, 909120094, 730871576, 196126022, 588378066, 766889845, 304180829, 912542487, 741138755, 226927559, 680782677, 45859325, 137577975, 412733925, 239957422, 719872266, 163128092, 489384276, 469908475, 411481072, 236198863, 708596589, 129301061, 387903183, 165465196, 496395588, 490942411, 474582880, 425504287, 278268508, 834805524, 507927866, 525539245, 578373382, 736875793, 214138673, 642416019, 929003704, 790522406, 375078512, 126991183, 380973549, 144676294, 434028882, 303842293, 911526879, 738091931, 217787087, 653361261, 961839430, 889029584, 670600046, 15311432, 45934296, 137802888, 413408664, 241981639, 725944917, 181346045, 544038135, 633870052, 903365803, 713608703, 144337403, 433012209, 300792274, 902376822, 710641760, 135436574, 406309722, 220684813, 662054439, 987918964, 967268186, 905315852, 719458850, 161887844, 485663532, 458746243, 377994376, 135738775, 407216325, 223404622, 670213866, 14152892, 42458676, 127376028, 382128084, 148139899, 444419697, 335014738, 6799861, 20399583, 61198749, 183596247, 550788741, 654121870, 964121257, 895875065, 691136489, 76920761, 230762283, 692286849, 80371841, 241115523, 723346569, 173551001, 520653003, 563714656, 692899615, 82210139, 246630417, 739891251, 223185047, 669555141, 12176717, 36530151, 109590453, 328771359, 986314077, 962453525, 890871869, 676126901, 31891997, 95675991, 287027973, 861083919, 586763051, 762044800, 289645694, 868937082, 610322540, 832723267, 501681095, 506798932, 522152443, 568212976, 706394575, 122695019, 368085057, 106010818, 318032454, 954097362, 865803380, 600921434, 804519949, 417071141, 252969070, 758907210, 280232924, 840698772, 525607610, 578578477, 737491078, 215984528, 647953584, 945616399, 840360491, 524592767, 575533948, 728357491, 188583767, 565751301, 699009550, 100539944, 301619832, 904859496, 718089782, 157780640, 473341920, 421781407, 267099868, 801299604, 407410106, 223985965, 671957895, 19384979, 58154937, 174464811, 523394433, 571938946, 717572485, 156228749, 468686247, 407814388, 225198811, 675596433, 30300593, 90901779, 272705337, 818116011, 457859327, 375333628, 127756531, 383269593, 151564426, 454693278, 365835481, 99262090, 297786270, 893358810, 683587724, 54274466, 162823398, 488470194, 467166229, 403254334, 211518649, 634555947, 905423488, 719781758, 162856568, 488569704, 467464759, 404149924, 214205419, 642616257, 929604418, 792324548, 380484938, 143210461, 429631383, 290649796, 871949388, 619359458, 859834021, 583013357, 750795718, 255898448, 767695344, 306597326, 919791978, 762887228, 292172978]
ni=[1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 75497471, 150994942, 301989884, 603979768, 209715183, 419430366, 838860732, 679477111, 360709869, 721419738, 444595123, 889190246, 780136139, 562027925, 125811497, 251622994, 503245988, 8247623, 16495246, 32990492, 65980984, 131961968, 263923936, 527847872, 57451391, 114902782, 229805564, 459611128, 919222256, 840200159, 682155965, 366067577, 732135154, 466025955, 932051910, 865859467, 733474581, 468704809, 937409618, 876574883, 754905413, 511566473, 24888593, 49777186, 99554372, 199108744, 398217488, 796434976, 594625599, 191006845, 382013690, 764027380, 529810407, 61376461, 122752922, 245505844, 491011688, 982023376, 965802399, 933360445, 868476537, 738708721, 479173089, 958346178, 918448003, 838651653, 679058953, 359873553, 719747106, 441249859, 882499718, 766755083, 535265813, 72287273, 144574546, 289149092, 578298184, 158352015, 316704030, 633408060, 268571767, 537143534, 76042715, 152085430, 304170860, 608341720, 218439087, 436878174, 873756348, 749268343, 500292333, 2340313, 4680626, 9361252, 18722504, 37445008, 74890016, 149780032, 299560064, 599120128, 199995903, 399991806, 799983612, 601722871, 205201389, 410402778, 820805556, 643366759, 288489165, 576978330, 155712307, 311424614, 622849228, 247454103, 494908206, 989816412, 981388471, 964532589, 930820825, 863397297, 728550241, 458856129, 917712258, 837180163, 676115973, 353987593, 707975186, 417706019, 835412038, 672579723, 346915093, 693830186, 389416019, 778832038, 559419723, 120595093, 241190186, 482380372, 964760744, 931277135, 864309917, 730375481, 462506609, 925013218, 851782083, 705319813, 412395273, 824790546, 651336739, 304429125, 608858250, 219472147, 438944294, 877888588, 757532823, 516821293, 35398233, 70796466, 141592932, 283185864, 566371728, 134499103, 268998206, 537996412, 77748471, 155496942, 310993884, 621987768, 245731183, 491462366, 982924732, 967605111, 936965869, 875687385, 753130417, 508016481, 17788609, 35577218, 71154436, 142308872, 284617744, 569235488, 140226623, 280453246, 560906492, 123568631, 247137262, 494274524, 988549048, 978853743, 959463133, 920681913, 843119473, 687994593, 377744833, 755489666, 512734979, 27225605, 54451210, 108902420, 217804840, 435609680, 871219360, 744194367, 490144381, 980288762, 962333171, 926421989, 854599625, 710954897, 423665441, 847330882, 696417411, 394590469, 789180938, 580117523, 161990693, 323981386, 647962772, 297681191, 595362382, 192480411, 384960822, 769921644, 541598935, 84953517, 169907034, 339814068, 679628136, 361011919, 722023838, 445803323, 891606646, 784968939, 571693525, 145142697, 290285394, 580570788, 162897223, 325794446, 651588892, 304933431, 609866862, 221489371, 442978742, 885957484, 773670615, 549096877, 99949401, 199898802, 399797604, 799595208, 600946063, 203647773, 407295546, 814591092, 630937831, 263631309, 527262618, 56280883, 112561766, 225123532, 450247064, 900494128, 802743903, 607243453, 216242553, 432485106, 864970212, 731696071, 465147789]
mod=998244353
n=int(input())
l=[None for i in range(n)]
for i in range(n):
    l[i]=int(input())
sl=sum(l)
l.sort()
ll=[[0 for i in range(n+1)] for i in range(sl+1)]
ll[0][0]=1
jmin=[400 for i in range(sl+1)]
jmax=[1 for i in range(sl+1)]
imax=0
jmin[0]=0
for a in l:
    for i in range(imax,-1,-1):
        if jmax[i+a] < jmax[i] + 1:
            jmax[i+a] = jmax[i] + 1
        if jmin[i+a] > jmin[i]:
            jmin[i+a] = jmin[i] + 1
        for j in range(jmin[i],jmax[i]):
            ll[i+a][j+1]+=ll[i][j]
    imax+=a
ans=(san[n]+mod+mod-ni[n]*3+3)%mod
lo=sl//2+1 if sl%2==1 else sl//2
for i in range(lo,sl+1):
    for j in range(1,n-1):
        ans+=mod+mod+mod-ll[i][j]*(ni[n-j-1]-1)*6
        ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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()
# start_time = time.time()
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, 4, 1 + (sum_a+1)//2), dtype=int)
dp[0, 3, 0] = 1

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

    # 緑に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 2, :]
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 3, :]

    # 青に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 1, :]
    dp[i, 2, :] += dp[i-1, 2, :]
    dp[i, 2, :] += dp[i-1, 3, :]

    # # まとめる ---> 数ms...あまり寄与せず
    # dp[:, i, 0] = dp[:, i, 0] + dp[:, i-1, 0]*2 + dp[:, i-1, 2] + dp[:, i-1, 1]
    # dp[:, i, 1] = dp[:, i, 1] + dp[:, i-1, 1] + dp[:, i-1, 3]
    # dp[:, i, 2] = dp[:, i, 2] + dp[:, i-1, 2] + dp[:, i-1, 3]

    if i % 15 == 0:
        dp %= MOD

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

Submission status: Time Limit Exceeded

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()
# start_time = time.time()
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, 4, 1 + (sum_a+1)//2), dtype=int)
dp[0, 3, 0] = 1

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

    # 緑に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 2, :]
    dp[i, 1, :] += dp[i-1, 1, :]
    dp[i, 1, :] += dp[i-1, 3, :]

    # 青に入れる
    dp[i, 0, :] += dp[i-1, 0, :]
    dp[i, 0, :] += dp[i-1, 1, :]
    dp[i, 2, :] += dp[i-1, 2, :]
    dp[i, 2, :] += dp[i-1, 3, :]

    # # まとめる ---> 数ms...あまり寄与せず
    # dp[:, i, 0] = dp[:, i, 0] + dp[:, i-1, 0]*2 + dp[:, i-1, 2] + dp[:, i-1, 1]
    # dp[:, i, 1] = dp[:, i, 1] + dp[:, i-1, 1] + dp[:, i-1, 3]
    # dp[:, i, 2] = dp[:, i, 2] + dp[:, i-1, 2] + dp[:, i-1, 3]

    if i % 10 == 0:
        dp %= MOD

dp %= MOD
# print((total - dp[-1, 0, (sum_a+1)//2:].sum() * 3) % MOD)
print((total - dp[-1, 0, -1].sum() * 3) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N = int(input())
A = np.asarray([int(input()) for _ in range(N)], dtype=np.int64)

sum_A = A.sum()
MOD = 998244353

dp1 = np.zeros(sum_A + 1, dtype=np.int64)
dp2 = np.zeros(sum_A + 1, dtype=np.int64)
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
        dp1[i + a] += dp1[i]
        dp1[i] <<= 1
        dp2[i + a] += dp2[i]
    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)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

N = int(input())
a = [int(input()) for _ in range(N)]
acc = [0 for _ in range(N + 1)]
for i in range(N):
    acc[i + 1] = acc[i] + a[i]

# dp[i][j][k] (0 <= i <= N, 0 <= j <= i, 0 <= k <= acc[i])
# は a[0],a[1],...,a[i-1] の中から j 個選んで和が k になるものの総数.
dp = [[[None for k in range(acc[i] + 1)] for j in range(i + 1)] for i in range(N + 1)]

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

def fdp(i, j, k):
    #print("in fdp: (i, j, k) = ({}, {}, {})".format(i, j, k))
    if i < 0 or j < 0 or i < j or k < 0 or acc[i] < k:
        return 0
    if dp[i][j][k] is not None:
        return dp[i][j][k]
    result = fdp(i - 1, j, k) + fdp(i - 1, j - 1, k - a[i - 1])
    dp[i][j][k] = result
    return result

not_triangle = 0
for k in range((acc[N] + 1) // 2, acc[N] + 1):
    for j in range(N + 1):
        not_triangle = (not_triangle + fdp(N, j, k) * (pow(2, N - j, MOD) - 0)) % MOD

if acc[N] % 2 == 0:
    overlap = 0
    for j in range(N + 1):
        overlap += fdp(N, j, acc[N] // 2)
    #print("overlap =", overlap)
    not_triangle -= overlap
not_triangle *= 3
#print("not_triangle =", not_triangle)
result = (pow(3, N) - not_triangle) % MOD
print(result)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
suma = sum(a)
suma2 = suma // 2
mod = 998244353

dp1 = [3] + [0] * suma2
dp2 = [3] + [0] * suma2
for ai in a:
    for j in range(suma2, ai - 1, -1):
        dp1[j] = (dp1[j] + dp1[j - ai] * 2) % mod
        dp2[j] = (dp2[j] + dp2[j - ai]    ) % mod
half = dp2[suma2] if suma % 2 == 0 else 0
print(((3 ** n) - sum(dp1) + half + mod) % mod)

Submission status: Time Limit Exceeded

Solution code:
N, *A = map(int, open(0).read().split())
MOD = 998244353

S = sum(A)
dp0 = [0]*(S+1)
dp0[0] = 1
dp1 = [0]*(S+1)
dp1[0] = 1
for a in A:
    for i in range(S, a-1, -1):
        dp0[i] = (dp0[i] + dp0[i-a]*2) % MOD
        dp1[i] = (dp1[i] + dp1[i-a]) % MOD

ans = pow(3, N, MOD)
for L in range(0, S+1):
    if L <= S-L:
        ans = (ans - dp0[L]*3) % MOD
if S % 2 == 0:
    ans = (ans + dp1[S//2]*3) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = sorted([int(input()) for _ in range(n)], reverse=True)
suma = sum(a)
mod = 998244353

dp1 = [3] + [0] * (suma // 2)
dp2 = [3] + [0] * (suma // 2)
for ai in a:
    for j in range(suma // 2, -1, -1):
        dp1[j] = (dp1[j] + (dp1[j - ai]  * 2 if j >= ai else 0)) % mod
        dp2[j] = (dp2[j] + (dp2[j - ai]      if j >= ai else 0)) % mod
half = dp2[suma // 2] if suma % 2 == 0 else 0
print(((3 ** n) - sum(dp1) + half + mod) % mod)

Submission status: Time Limit Exceeded

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

N=int(input())
A=[int(input()) for i in range(N)]
SUM=sum(A)
MAX=(SUM-1)//2

mod=998244353
from collections import Counter

DPLIST=[[0]*301 for i in range(MAX+2)]
DPLIST[0][0]=1
ANS=0

for a in A:
    for i in range(299,-1,-1):
        for j in range(MAX+1,-1,-1):
            DPLIST[min(j+a,MAX+1)][i+1]+=DPLIST[j][i]

ANS=(pow(3,N,mod)-3*pow(2,N,mod))%mod
MINUS=0

for i in range(N-1):
    MINUS+=3*(pow(2,(N-i),mod)-2)*DPLIST[MAX+1][i]

print((ANS-MINUS+3)%mod)

Submission status: Time Limit Exceeded

Solution code:
DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)
dp = [[0] * (suma+1) for i in range(N)]
dp2 = [[0] * (suma+1) for i in range(N)]
dp[0][0] = 2
dp[0][a[0]] = 1
dp2[0][0] = 1
dp2[0][a[0]] = 1 
allc = 3
flag = 0
if(suma%2 == 0):
	flag = 1
for i in range(1,N):
	allc = allc*3
	k = a[i]
	for j in range(sum(a[:i+1])+1):
		if(j < k):
			dp[i][j] = dp[i-1][j]*2
			if(flag == 1):
				dp2[i][j] = dp2[i-1][j]
		else:
			dp[i][j] = dp[i-1][j]*2+dp[i-1][j-k]
			if(flag == 1):
				dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-k]
allc = allc - sum(dp[N-1][suma-suma/2:])*3
if(flag == 1):			
	allc += dp2[N-1][suma/2]*3
print(allc%DIV)

Submission status: Time Limit Exceeded

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

for a in A:
    dp1_ = [0] * (sum_A + 1)
    dp2_ = [0] * (sum_A + 1)
    for i in range(sum_A + 1):
        # R に塗った場合
        if i + a <= sum_A:
            dp1_[i + a] += dp1[i]
            dp2_[i + a] += dp2[i]
        # G, B に塗った場合
        dp1_[i] += dp1[i] * 2
        dp2_[i] += dp2[i]
    dp1 = dp1_
    dp2 = dp2_

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

Submission status: Time Limit Exceeded

Solution code:
DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort()
suma = sum(a)
dp = [[0] * (suma+1) for i in range(N)]
dp[0][0] = 2
dp[0][a[0]] = 1
allc = 3
for i in range(1,N):
	allc = allc*3
	k = a[i]
	for j in range(sum(a[:i+1])+1):
		if(j < k):
			dp[i][j] = dp[i-1][j]*2
		else:
			dp[i][j] = dp[i-1][j]*2+dp[i-1][j-k]
allc = allc - sum(dp[N-1][suma-suma/2:])*3
if(suma%2 == 0):
	dp2 = [[0] * (suma+1) for i in range(N)]
	dp2[0][0] = 1
	dp2[0][a[0]] = 1 
	for i in range(1,N):
		k = a[i]
		for j in range(sum(a[:i+1])+1):
			if(j < k):
				dp2[i][j] = dp2[i-1][j]
			else:
				dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-k]
	allc += dp2[N-1][suma/2]*3
print(allc%DIV)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

# dp[i][j][k] (0 <= i <= N, 0 <= j <= i, 0 <= k <= total)
# は a[0],a[1],...,a[i-1] の中から j 個選んで和が k になるものの総数.
dp = [[[0 for k in range(total + 1)] for j in range(N + 1)] for i in range(N + 1)]
for i in range(N + 1):
    dp[i][0][0] = 1

for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(total + 1):
            dp[i][j][k] = dp[i - 1][j][k]
            if k >= a[i - 1]:
                dp[i][j][k] += dp[i - 1][j - 1][k - a[i - 1]]
            #print("dp[{}][{}][{}] = {}".format(i, j, k, dp[i][j][k]))

not_triangle = 0
for k in range((total + 1) // 2, total + 1):
    for j in range(N + 1):
        not_triangle = (not_triangle + dp[N][j][k] * (pow(2, N - j, MOD) - 0)) % MOD

if total % 2 == 0:
    overlap = 0
    for j in range(N + 1):
        overlap += dp[N][j][total // 2]
    #print("overlap =", overlap)
    not_triangle -= overlap
not_triangle *= 3
#print("not_triangle =", not_triangle)
result = (pow(3, N) - not_triangle) % MOD
print(result)