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:
from collections import defaultdict

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

DP = [defaultdict(int)]
DP[0][0] = 2
DP[0][A[0]] = 1
DP2 = [defaultdict(int)]  # R=G=S/2, B=0
DP2[0][0] = 1
DP2[0][A[0]] = 1
for i in range(1, N):
    curr = defaultdict(int)
    curr2 = defaultdict(int)
    for (key, val) in DP[-1].items():
        curr[key] += val*2  # B,G
        curr[key+A[i]] += val  # R
    for (key, val) in DP2[-1].items():
        curr2[key] += val  # G
        curr2[key+A[i]] += val  # R
    DP.append(curr)
    DP2.append(curr2)
# print(DP)
# print(DP2)

ans = 3**N
for (key, val) in DP[-1].items():
    if key >= S/2:
        ans -= 3*val

if S % 2 == 0:
    ans += 3*DP2[-1][S//2]

print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
MOD = 998244353
n = int(input())
a = [int(input()) for _ in range(n)]
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 j in range(s+1):
		dp[i+1][j] += dp[i][j] * 2
		dp[i+1][j] %= MOD
		if j+a[i] <= s:
			dp[i+1][j+a[i]] += dp[i][j]
			dp[i+1][j+a[i]] %= MOD
#print(*dp, sep="\n")
res = 0
for j in range(s+1):
	if j*2 >= s:
		res += dp[n][j] * 3
		res %= MOD

if s%2 == 0:
	dpp = [0 for _ in range(s+1)]
	dpp[0] = 1
	for i in range(n):
		for j in range(s-a[i], -1, -1):
			dpp[j+a[i]] += dpp[j]
			dpp[j+a[i]] %= MOD
	res -= dpp[s//2] * 3

print((pow(3, n, MOD) - res) % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

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


def main():

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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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


def main():

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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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


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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:

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


def main():

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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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


def main():

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

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

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

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

        for length in range(min(sum_now + 1, sum_A // 2 + 1)):
            if length >= a:
                dp2[i][length] = (dp2[i - 1][length - a] +
                                  dp2[i - 1][length]) % mod
            else:
                dp2[i][length] = dp2[i-1][length]

    # print(sum(dp[N-1][sum_A//2]))
    # print(dp)
    ans -= 3*sum(dp[N-1][(sum_A+1)//2:])
    if sum_A % 2 == 0:
        ans += 3*dp2[N-1][sum_A//2]
    print(ans % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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


def main():

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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


def main():

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

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


def main():

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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

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

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

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

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

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

for k in range(N):
    for i in range(k,-1,-1):
        for j in range(MAX+1,-1,-1):
            DPLIST[min(j+A[k],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:
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

DPLIST=[0]*(MAX+2)
DPLIST[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        if i==MAX+1:
            DPLIST[i]=DPLIST[i]*3%mod
        else:
            DPLIST[min(i+a,MAX+1)]=(DPLIST[min(i+a,MAX+1)]+DPLIST[i])%mod
            DPLIST[i]=DPLIST[i]*2%mod

if SUM%2==1:
    print((sum(DPLIST)-DPLIST[-1]*3)%mod)
    sys.exit()

MAX=SUM//2
       
DPLIST2=[0]*(MAX+2)
DPLIST2[0]=1

for a in A:
    for i in range(MAX+1,-1,-1):
        DPLIST2[min(i+a,MAX+1)]=(DPLIST2[min(i+a,MAX+1)]+DPLIST2[i])%mod

        
print((sum(DPLIST)-DPLIST[-1]*3+DPLIST2[-2]*3)%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

c10 = [0] * (m + 1)
c1 = array.array('l', c10)
c1[m] = 1
for i in range(N):
    d = a[i]
    for j in range(m - d + 1):
        c1[j] = (2 * c1[j] + c1[j + d]) % 998244353
    for j in range(m - d + 1, m + 1):
        c1[j] = (2 * c1[j] + c1[m]) % 998244353

ans1 = c1[0]

if s % 2:
    c1[0] = 0
else:
    for j in range(m):
        c1[j] = 0
    c1[m] = 1
    for i in range(N):
        d = a[i]
        for j in range(m - d + 1):
            c1[j] = (c1[j] + c1[j + d]) % 998244353
        for j in range(m - d + 1, m + 1):
            c1[j] = c1[j]

ans = (3 ** N % 998244353 - 3 * ans1 + 3 * c1[0]) % 998244353
print(ans)

Submission status: Time Limit Exceeded

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

c1 = [0] * (m + 1)
c1[m] = 1
for i in range(N):
    d = a[i]
    for j in range(m - d + 1):
        c1[j] = (2 * c1[j] + c1[j + d]) % 998244353
    for j in range(m - d + 1, m + 1):
        c1[j] = (2 * c1[j] + c1[m]) % 998244353

ans1 = c1[0]

if s % 2:
    c1[0] = 0
else:
    for j in range(m):
        c1[j] = 0
    c1[m] = 1
    for i in range(N):
        d = a[i]
        for j in range(m - d + 1):
            c1[j] = (c1[j] + c1[j + d]) % 998244353
        for j in range(m - d + 1, m + 1):
            c1[j] = c1[j]

ans = (3 ** N % 998244353 - 3 * ans1 + 3 * c1[0]) % 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(2)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(2)]
    dp2[0][0] = 1
    for i in range(N):
        dp1[(i+1) & 1] = defaultdict(lambda: 0)
        dp2[(i+1) & 1] = defaultdict(lambda: 0)
        for j in dp1[i & 1]:
            nj = min(j+A[i], half+1)
            dp1[(i+1) & 1][j] = (dp1[(i+1) & 1][j] + dp1[i & 1][j] * 2) % MOD
            dp1[(i+1) & 1][nj] = (dp1[(i+1) & 1][nj] + dp1[i & 1][j]) % MOD
            dp2[(i+1) & 1][j] = (dp2[(i+1) & 1][j] + dp2[i & 1][j]) % MOD
            dp2[(i+1) & 1][nj] = (dp2[(i+1) & 1][nj] + dp2[i & 1][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N & 1]:
        if t >= -(-total//2):
            ans = (ans - dp1[N & 1][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N & 1][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/tenka1-2019/submissions/5065329

import sys

input = sys.stdin.readline

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

'''(1)全体'''
U = pow(3, N, MOD)  # 三角形を構成できない場合を含むRGBの組み合わせ総数

'''(2)単円'''
dp = [[0] * (total + 1) for _ in range(N + 1)]
dp[0][0] = 1
# dp[i][R]:=i番目まででRとなる場合の数

for i in range(N):
    for r in range(total + 1):
        if r - a[i] >= 0:
            dp[i + 1][r] += dp[i][r - a[i]]
        dp[i + 1][r] += 2 * dp[i][r]
        # g, bに加算する分で、2回起こる
# print(dp)

single_circle = 0
for r in range(total + 1):
    if r >= (total / 2):
        single_circle += dp[N][r]
# print(single_circle)

'''(3)２円の積集合'''
if total % 2 == 0:
    dp2 = [[0] * (total + 1) for _ in range(N + 1)]
    dp2[0][0] = 1
    # dp[i][R]:=i番目まででRとなる場合の数

    for i in range(N):
        for r in range(int(total / 2) + 1):
            if r - a[i] >= 0:
                dp2[i + 1][r] += dp2[i][r - a[i]]
            dp2[i + 1][r] += dp2[i][r]
    # print(dp2)

two_circle_intersect = dp2[N][int(total / 2)] if total % 2 == 0 else 0

'''(3)３円の積集合'''
three_circle_intersect = 0

'''(4)解答'''
ans = 0

ans += U
ans %= MOD

ans -= 3 * single_circle
ans %= MOD

ans += 3 * two_circle_intersect
ans %= MOD

ans -= three_circle_intersect
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

MOD = 998244353


def main():
    N = int(input())
    A = [int(input()) for _ in range(N)]
    total = sum(A)
    half = -(-total//2)
    dp1 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp1[0][0] = 1
    dp2 = [defaultdict(lambda: 0) for _ in range(N+1)]
    dp2[0][0] = 1
    for i in range(N):
        for j in dp1[i]:
            nj = min(j+A[i], half+1)
            dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j] * 2) % MOD
            dp1[i+1][nj] = (dp1[i+1][nj] + dp1[i][j]) % MOD
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % MOD
            dp2[i+1][nj] = (dp2[i+1][nj] + dp2[i][j]) % MOD
    ans = (3**N) % MOD
    for t in dp1[N]:
        if t >= -(-total//2):
            ans = (ans - dp1[N][t] * 3) % MOD
            if total % 2 == 0 and t == total // 2:
                ans = (ans + dp2[N][t] * 3) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from math import ceil


def solve():
    # 入力
    N = int(input())
    A = [int(input()) for i in range(N)]

    MOD = 998244353

    class ModInt:
        def __init__(self, x):
            self.x = x % MOD

        def __str__(self):
            return str(self.x)

        __repr__ = __str__

        def __add__(self, other):
            return (
                ModInt(self.x + other.x) if isinstance(other, ModInt) else
                ModInt(self.x + other)
            )

        def __sub__(self, other):
            return (
                ModInt(self.x - other.x) if isinstance(other, ModInt) else
                ModInt(self.x - other)
            )

        def __mul__(self, other):
            return (
                ModInt(self.x * other.x) if isinstance(other, ModInt) else
                ModInt(self.x * other)
            )

        def __truediv__(self, other):
            return (
                ModInt(
                    self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

        def __pow__(self, other):
            return (
                ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(self.x, other, MOD))
            )

        __radd__ = __add__

        def __rsub__(self, other):
            return (
                ModInt(other.x - self.x) if isinstance(other, ModInt) else
                ModInt(other - self.x)
            )

        __rmul__ = __mul__

        def __rtruediv__(self, other):
            return (
                ModInt(
                    other.x * pow(self.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )

        def __rpow__(self, other):
            return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
            )

    S = sum(A)
    # 赤色の整数の和がiとなるような塗り方の個数
    dp = [ModInt(0) for _ in range(S + 1)]
    dp[0] = ModInt(1)
    # 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
    dp2 = [ModInt(0) for _ in range(S // 2 + 1)]
    dp2[0] = ModInt(1)

    # 動的計画法により、dp, dp2を求める
    for a in A:
        for i in range(S, a - 1, -1):
            dp[i] = dp[i] * 2 + dp[i - a]
        for i in range(a - 1, -1, -1):
            dp[i] = dp[i] * 2
        for i in range(S // 2, a - 1, -1):
            dp2[i] = dp2[i] + dp2[i - a]

    # 全ての塗り方の個数から、条件を満たさない塗り方の個数を差し引いて解を求める
    ans = 3**N - 3 * sum(dp[ceil(S / 2):]) + (
        3 * dp2[S // 2] if S % 2 == 0 else
        0
    )

    # 出力
    print(ans)


solve()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
z,s=1,0
d=[1]+[0]*7**6
e=d[:]
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
print(z+~s%2*e[s//2]*3-3*sum(d[-~s//2:]))%998244353

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

# 入力
N = int(input())
A = [int(input()) for i in range(N)]

MOD = 998244353


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


S = sum(A)
# 赤色の整数の和がiとなるような塗り方の個数
dp = [ModInt(0) for _ in range(S + 1)]
dp[0] = ModInt(1)
# 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
dp2 = [ModInt(0) for _ in range(S // 2 + 1)]
dp2[0] = ModInt(1)

# 動的計画法により、dp, dp2を求める
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = dp[i] * 2 + dp[i - a]
    for i in range(a - 1, -1, -1):
        dp[i] = dp[i] * 2
    for i in range(S // 2, a - 1, -1):
        dp2[i] = dp2[i] + dp2[i - a]

# 全ての塗り方の個数から、条件を満たさない塗り方の個数を差し引いて解を求める
ans = 3**N - 3 * sum(dp[ceil(S / 2):]) + (
    3 * dp2[S // 2] if S % 2 == 0 else
    0
)

# 出力
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

# 入力
N = int(input())
A = [int(input()) for i in range(N)]

MOD = 998244353


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


S = sum(A)
# 赤色の整数の和がiとなるような塗り方の個数
dp = [ModInt(0) for _ in range(S + 1)]
dp[0] = ModInt(1)
# 赤色の整数の和がi, 他の整数がすべて青色となるような塗り方の個数
dp2 = [ModInt(0) for _ in range(S // 2 + 1)]
dp2[0] = ModInt(1)

# 動的計画法により、dp, dp2を求める
for a in A:
    for i in range(S, a - 1, -1):
        dp[i] = 2 * dp[i] + dp[i - a]
    for i in range(a - 1, -1, -1):
        dp[i] = 2 * dp[i]
    for i in range(S // 2, a - 1, -1):
        dp2[i] = dp2[i] + dp2[i - a]

# 全ての塗り方の個数から、条件を満たさない塗り方の個数を差し引いて解を求める
ans = 3**N - 3 * sum(dp[i] for i in range(ceil(S / 2), S + 1)) + (
    3 * dp2[S // 2] if S % 2 == 0 else
    0
)

# 出力
print(ans)

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]%M;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:
M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);s+=a;i=s;z*=3
	while~i:d[i]+=d[i]+d[i-a]%M;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:
M=998244353
N,*A=open(0)
d=[1]+[0]*7**6
e=[1]+[0]*7**6
z=1
s=0
for a in A:
	a=int(a);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)