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:
DIV = 998244353

N = input()
a = []
for i in range(N):
    a.append(input())
count = 0
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:
N = int(input())
A = [int(input()) for i in range(N)]
MOD = 998244353

S = sum(A)

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

dp2 = [[0]*(S+1) for _ in range(N+1)]
dp2[0][0] = 1

for i in range(N):
    a = A[i]
    x = 0
    while x <= S:
        if x + a <= S:
            dp[i+1][x+a] += dp[i][x]
            dp2[i+1][x+a] += dp2[i][x]
        dp[i+1][x] += dp[i][x] * 2
        dp2[i+1][x] += dp2[i][x]
        x += 1



if S % 2 == 0:
    ans = 3 ** N - sum(dp[N][S//2:]) * 3
    ans += 3 * dp2[N][S//2]
else:
    ans = 3 ** N - sum(dp[N][S//2 + 1:]) * 3

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys

n = int(input())
aaa = list(map(int, sys.stdin))
MOD = 998244353

s = sum(aaa)
dp1 = [0] * (s + 1)
dp2 = [0] * (s + 1)
dp1[0] = 1
dp2[0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dp1[i + a] += dp1[i]
        dp1[i] *= 2
        dp2[i + a] += dp2[i]
    for i in range(tmp_sum, -1, -1):
        dp1[i] %= MOD
        dp2[i] %= MOD
    tmp_sum += a

h = (s + 1) // 2
ans = (pow(3, n, MOD) - sum(dp1[h:]) * 3) % MOD
if s % 2 == 0:
    ans = (ans + dp2[h] * 3) % 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

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

sum_a = 0
for i in range(1, N+1):
    a = d_in()
    sum_a += a
    # 赤に入れる
    dp[a:, i, :] += dp[:-a, i-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]
    if i % 10 == 0:
        dp %= MOD


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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
vals = []
for _ in range(N):
	vals.append(int(input()))

vals = sorted(vals)
total_val = sum(vals)
ans_dict_bigger={}
ans_dict_eq_2={}
rest_vals = [sum(vals[i:]) for i in range(N)]

def calc_bigger(i,r):
	if i == N:
		return 1 if r >=total_val/2 else 0
	
	if r >=total_val/2:
		return 3 ** (N-i)
	
	if r + rest_vals[i] < total_val/2:
		return 0
	
	if (i,r) in ans_dict_bigger.keys():
		return ans_dict_bigger[(i,r)]
	

	ret = calc_bigger(i+1,r+vals[i]) + 2*calc_bigger(i+1,r)
	ans_dict_bigger[(i,r)] = ret
	return ret


def calc_eq_2(i,r):
	if i == N:
		return 1 if r ==total_val/2 else 0
	
	if r > total_val/2:
		return 0
	
	if r + rest_vals[i] < total_val/2:
		return 0
	
	if (i,r) in ans_dict_eq_2.keys():
		return ans_dict_eq_2[(i,r)]
	

	ret = calc_eq_2(i+1,r+vals[i]) + calc_eq_2(i+1,r)
	ans_dict_eq_2[(i,r)] = ret
	return ret

if total_val % 2 == 0:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))
else:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0))

print(ptn_num % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
vals = []
for _ in range(N):
	vals.append(int(input()))

vals = sorted(vals)
vals.reverse()
total_val = sum(vals)
ans_dict_bigger={}
ans_dict_eq_2={}
rest_vals = [sum(vals[i:]) for i in range(N)]

def calc_bigger(i,r):
	if i == N:
		return 1 if r >=total_val/2 else 0
	
	if r >=total_val/2:
		return 3 ** (N-i)
	
	if r + rest_vals[i] < total_val/2:
		return 0
	
	if (i,r) in ans_dict_bigger.keys():
		return ans_dict_bigger[(i,r)]
	

	ret = calc_bigger(i+1,r+vals[i]) + 2*calc_bigger(i+1,r)
	ans_dict_bigger[(i,r)] = ret
	return ret


def calc_eq_2(i,r):
	if i == N:
		return 1 if r ==total_val/2 else 0
	
	if r > total_val/2:
		return 0
	
	if r + rest_vals[i] < total_val/2:
		return 0
	
	if (i,r) in ans_dict_eq_2.keys():
		return ans_dict_eq_2[(i,r)]
	

	ret = calc_eq_2(i+1,r+vals[i]) + calc_eq_2(i+1,r)
	ans_dict_eq_2[(i,r)] = ret
	return ret

if total_val % 2 == 0:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))
else:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0))

print(ptn_num % 998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
S = sum(A)

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

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(PS[i]+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] = (D[i+1][j] + D[i][j] * 2) % mod
        D[i+1][j+A[i]] = (D[i+1][j+A[i]] + D[i][j]) % mod

for i in range(N):
    for j in range(PS[i]+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] = (D2[i+1][j] + D2[i][j]) % mod
        D2[i+1][j+A[i]] = (D2[i+1][j+A[i]] + D2[i][j]) % mod

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
S = sum(A)

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

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(PS[i]+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(PS[i]+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] += D[i][j] * 2
        D[i+1][j+A[i]] += D[i][j]

for i in range(N):
    for j in range(PS[i]+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] += D2[i][j]
        D2[i+1][j+A[i]] += D2[i][j]

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % 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)

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


MOD = 998244353

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

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

sum_a = 0
for i in range(1, N+1):
    a = d_in()
    sum_a += a
    # 赤に入れる
    dp[a:, i, :] += dp[:-a, i-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]
    dp %= MOD


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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
vals = []
for _ in range(N):
	vals.append(int(input()))

vals = sorted(vals)

total_val = sum(vals)
ans_dict_bigger={}
ans_dict_eq_2={}

def calc_bigger(i,r):
	if i == N:
		return 1 if r >=total_val/2 else 0
	
	if (i,r) in ans_dict_bigger.keys():
		return ans_dict_bigger[(i,r)]
	

	ret = calc_bigger(i+1,r+vals[i]) + 2*calc_bigger(i+1,r)
	ans_dict_bigger[(i,r)] = ret
	return ret


def calc_eq_2(i,r):
	if i == N:
		return 1 if r ==total_val/2 else 0
		
	if (i,r) in ans_dict_eq_2.keys():
		return ans_dict_eq_2[(i,r)]
	

	ret = calc_eq_2(i+1,r+vals[i]) + calc_eq_2(i+1,r)
	ans_dict_eq_2[(i,r)] = ret
	return ret

if total_val % 2 == 0:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))
else:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0))

print(ptn_num % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
vals = []
for _ in range(N):
	vals.append(int(input()))

vals = sorted(vals)
vals.reverse()
total_val = sum(vals)
ans_dict_bigger={}
ans_dict_eq_2={}

def calc_bigger(i,r):
	if i == N:
		return 1 if r >=total_val/2 else 0
	
	if (i,r) in ans_dict_bigger.keys():
		return ans_dict_bigger[(i,r)]
	

	ret = calc_bigger(i+1,r+vals[i]) + 2*calc_bigger(i+1,r)
	ans_dict_bigger[(i,r)] = ret
	return ret


def calc_eq_2(i,r):
	if i == N:
		return 1 if r ==total_val/2 else 0
		
	if (i,r) in ans_dict_eq_2.keys():
		return ans_dict_eq_2[(i,r)]
	

	ret = calc_eq_2(i+1,r+vals[i]) + calc_eq_2(i+1,r)
	ans_dict_eq_2[(i,r)] = ret
	return ret

if total_val % 2 == 0:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))
else:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0))

print(ptn_num % 998244353)

Submission status: Time Limit Exceeded

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

n = int(input())
a = [int(input()) for i in range(n)]
w = sum(a)
mod =998244353

dp = [[0]*(w+1) for i in range(n)]

cnt = a[0]
dp[0][a[0]] = 1
dp[0][0] = 2
for i in range(1,n):
    cnt += a[i]
    for j in range(cnt+1):
        dp[i][j] = dp[i-1][j]*2
        if j >= a[i]:
            dp[i][j] += dp[i-1][j-a[i]]
        


#sより大きいのはブー
s = w//2+1
if w %2 == 0:
    d = [[0]*(s+1) for i in range(n)]
    d[0][0] = 1
    d[0][a[0]] = 1
    cnt = a[0]

    for i in range(1,n):
        cnt += a[i]
        for j in range(min(cnt+1,s+1)):
            d[i][j] = d[i-1][j]
            if j >= a[i]:
                d[i][j] += d[i-1][j-a[i]]
            d[i][j] = d[i][j]%mod
    mns = d[-1][w//2]
if w%2 == 0:
    s -= 1
cnt = 0
for i in range(s,w+1):
    cnt += dp[-1][i]
    cnt = cnt%mod

res = (pow(3,n,mod)-cnt*3)%mod

if w % 2 == 0:
    res = (res+mns*3)%mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
vals = []
for _ in range(N):
	vals.append(int(input()))

total_val = sum(vals)
ans_dict_bigger={}
ans_dict_eq_2={}

def calc_bigger(i,r):
	if i == N:
		return 1 if r >=total_val/2 else 0
	
	if (i,r) in ans_dict_bigger.keys():
		return ans_dict_bigger[(i,r)]
	

	ret = calc_bigger(i+1,r+vals[i]) + 2*calc_bigger(i+1,r)
	ans_dict_bigger[(i,r)] = ret
	return ret


def calc_eq_2(i,r):
	if i == N:
		return 1 if r ==total_val/2 else 0
		
	if (i,r) in ans_dict_eq_2.keys():
		return ans_dict_eq_2[(i,r)]
	

	ret = calc_eq_2(i+1,r+vals[i]) + calc_eq_2(i+1,r)
	ans_dict_eq_2[(i,r)] = ret
	return ret

if total_val % 2 == 0:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))
else:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0))

print(ptn_num % 998244353)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N = int(input())
A = [int(input()) for i in range(N)]
A.sort(reverse=True)
S = sum(A)

# D[i][r]: i個塗った時点でR=rとなる場合の数
D = [[0 for _ in range(S+1)] for i in range(N+1)]
D[0][0] = 1
# D2[i][r]: i個塗った時点でR=r, B=0となる場合の数
D2 = [[0 for _ in range(S+1)] for i in range(N+1)]
D2[0][0] = 1

for i in range(N):
    for j in range(S+1):
        if D[i][j] == 0:
            continue
        D[i+1][j] += D[i][j] * 2
        D[i+1][j+A[i]] += D[i][j]

for i in range(N):
    for j in range(S+1):
        if D2[i][j] == 0:
            continue
        D2[i+1][j] += D2[i][j]
        D2[i+1][j+A[i]] += D2[i][j]

border = (S + 1) // 2

result = 3 ** N
result -= 3 * sum(D[N][border:])
if border * 2 == S:
    result += 3 * D2[N][border]

print(result % mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
vals = []
for _ in range(N):
	vals.append(int(input()))

total_val = sum(vals)
ans_dict_bigger={}
ans_dict_eq_2={}

def calc_bigger(i,r):
	if (i,r) in ans_dict_bigger.keys():
		return ans_dict_bigger[(i,r)]
	
	if i == N:
		return 1 if r >=total_val/2 else 0

	ret = calc_bigger(i+1,r+vals[i]) + 2*calc_bigger(i+1,r)
	ans_dict_bigger[(i,r)] = ret
	return ret


def calc_eq_2(i,r):
	if (i,r) in ans_dict_eq_2.keys():
		return ans_dict_eq_2[(i,r)]
	
	if i == N:
		return 1 if r ==total_val/2 else 0

	ret = calc_eq_2(i+1,r+vals[i]) + calc_eq_2(i+1,r)
	ans_dict_eq_2[(i,r)] = ret
	return ret

if total_val % 2 == 0:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))
else:
	ptn_num = 3 ** N - 3*(calc_bigger(0,0))

print(ptn_num % 998244353)

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)
    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]:
            dp1[i+1][j] = (dp1[i+1][j] + dp1[i][j] * 2) % MOD
            dp1[i+1][j+A[i]] = (dp1[i+1][j+A[i]] + dp1[i][j]) % MOD
            dp2[i+1][j] = (dp2[i+1][j] + dp2[i][j]) % MOD
            dp2[i+1][j+A[i]] = (dp2[i+1][j+A[i]] + 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:
import sys
input=sys.stdin.readline
n=int(input())
a=[int(input()) for i in range(n)]
li=[[0,0]]
for i in a:
    li=li+[[j[0]+i,j[1]+1] for j in li]
li.sort(key=lambda x:x[0])
s=li[-1][0]
ans=3**n-2**n*3+3
ans%=998244353
for i in li:
    if i[0]<s/2:
        continue
    if i[1]==n:
        continue
    ans-=(2**(n-i[1])-2)*3
    ans%=998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 998244353  # type: int

def solve(N: int, a: "List[int]"):
    s = sum(a)
    dp = [[[0] * 2 for _ in range(s + 1)] for _ in range(N + 1)] # dp[idx][sum][]
    cum = [0] * N
    cum[0] = a[0]
    for i in range(N - 1):
        cum[i + 1] = cum[i] + a[i + 1]
    dp[0][0][0] = 1
    dp[0][0][1] = 1
    for i in range(N):
        for j in range(cum[i] + 1 - a[i]):
            dp[i + 1][j + a[i]][0] += dp[i][j][0]
            dp[i + 1][j + a[i]][1] += dp[i][j][1]
            dp[i + 1][j][0] += dp[i][j][0]
            dp[i + 1][j][1] += dp[i][j][1] * 2

    tmp = 0
    border = (s + 1) // 2
    uniq = 0
    #pprint(dp)
    for j in range(border, s + 1):
        tmp += dp[N][j][1]
        uniq += dp[N][j][0]
    #print(tmp, uniq)
    tmp -= uniq * 2
    tmp *= 3

    ret = (3 ** N) % MOD
    col_2 = (2 ** N) % MOD
    ret -= 3 + (col_2 - 2) * 3 + 3
    #print(ret)
    #for i in range(N):
    #    ret *= 3
    #    ret %= MOD
    #    col_2 *= 2
    #    col_2 %= MOD
    ret -= tmp
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 998244353  # type: int

def solve(N: int, a: "List[int]"):
    s = sum(a)
    dp = [[[0] * 2 for _ in range(s + 1)] for _ in range(N + 1)] # dp[idx][sum][]
    dp[0][0][0] = 1
    dp[0][0][1] = 1
    for i in range(N):
        for j in range(s + 1 - a[i]):
            dp[i + 1][j + a[i]][0] += dp[i][j][0]
            dp[i + 1][j + a[i]][1] += dp[i][j][1]
            dp[i + 1][j][0] += dp[i][j][0]
            dp[i + 1][j][1] += dp[i][j][1] * 2

    tmp = 0
    border = (s + 1) // 2
    uniq = 0
    #pprint(dp)
    for j in range(border, s + 1):
        tmp += dp[N][j][1]
        uniq += dp[N][j][0]
    #print(tmp, uniq)
    tmp -= uniq * 2
    tmp *= 3

    ret = (3 ** N) % MOD
    col_2 = (2 ** N) % MOD
    ret -= 3 + (col_2 - 2) * 3 + 3
    #print(ret)
    #for i in range(N):
    #    ret *= 3
    #    ret %= MOD
    #    col_2 *= 2
    #    col_2 %= MOD
    ret -= tmp
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

mod=998244353
from collections import Counter

NALL=Counter()
NALL[(0,0)]=1

ANS=0

for a in A:
    ALL=copy.deepcopy(NALL)
    for l,x in ALL:
        NALL[a+l,x+1]+=ALL[l,x]

    #print(NALL)

ANS=(pow(3,N,mod)-3*pow(2,N,mod))%mod
MINUS=0
for a,x in NALL:
    if MAX<a and N-x>=2:
        MINUS+=3*(pow(2,(N-x),mod)-2)*NALL[a,x]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
A = [int(input()) for n in range(N)]
mod = 998244353

def is_triangle(r, g, b):
    if r+g > b and g+b>r and b+r>g: return True
    else: return False

def search(i, r, g, b, memo = {}):
    col = [r, g, b]
    col.sort()
    s, m, l = col
    if i == N - 1:
        count = 0
        if is_triangle(s+A[i], m, l): count += 1
        if is_triangle(s, m+A[i], l):count += 1
        if is_triangle(s, m, l+A[i]): count += 1
        return count
    try:
        return memo[(i, s, m, l)]
    except KeyError:
        count = 0
        count += search(i+1, s + A[i], m, l, memo)
        count %= mod
        count += search(i+1, s, m + A[i], l, memo)
        count %= mod
        count += search(i+1, s, m, l + A[i], memo)
        count %= mod
        memo[(i, s, m, l)] = count
        return count

memo = {}
print(search(0, 0, 0, 0, memo))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [abs(int(input())) for _ in range(N)]
#A.sort()
s = sum(A)

def mulmod(p,q,mod):
  return ((p%mod)*(q%mod))%mod
def powermod(p,n,mod):
  if n==0: return 1
  if n==1: return p%mod
  else:    return powermod(p,n//2,mod)**2 * (p**(n%2)) %mod
def dividemod(p,q,mod):
  # modは素数
  return mulmod(p, powermod(q,mod-2,mod), mod)

mod = 998244353

import numpy as np

dp = [np.zeros(s+1) for _ in range(N)]


# dp[n][s] An-1(0-index)まで加えて、Rの和がsになるのが何通りか（残りのG,Bまで含めて）
dp[0][0] = 2
dp[0][A[0]] = 1
temp_sum = A[0]

for i in range(1,N):
  dp[i] = np.mod((np.roll(dp[i-1], A[i]) + dp[i-1]*2), mod)
  temp_sum += A[i]

def part_sum(a,A):
  p=mod
  #初期化
  N=len(a)
  dp=[[0 for i in range(A+1)] for j in range(N+1)]
  dp[0][0]=1

  #DP
  for i in range(N):
    for j in range(A+1):
      if a[i]<=j: #i+1番目の数字a[i]を足せるかも
        dp[i+1][j]=dp[i][j-a[i]]+ dp[i][j]% p
      else: #入る可能性はない
        dp[i+1][j]=dp[i][j]%p
  return dp[N][A]

ps = part_sum(A, s//2)

if s%2 != 0:
    answer = (powermod(3, N, mod) - 3*sum(dp[N-1][(s+1)//2:]))%mod
else:
    answer = (powermod(3, N, mod) - 3*(sum(dp[N-1][(s+1)//2:]) - ps))%mod

answer = int(answer)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np 

MOD = 998244353

def check(a,b,c):
  return 0 < b+c-a and 0 < a - np.abs(b-c) 

N=int(input())
a = np.empty(N, dtype=np.int)
for i in range(N):
  a[i]=int(input())

# N = 4
# a = np.array([1,1,1,2], dtype=np.int)


# N = 300
# a = np.array([1]*N, dtype=np.int)


dp = [{} for i in range(N+1)]
dp[0][(0,0,0)] = 1

for i in range(0,N):
    for k in dp[i]:
        for sw in [(1,0,0),(0,1,0),(0,0,1)]:
            new_k = (k[0]+sw[0]*a[i], k[1]+sw[1]*a[i], k[2]+sw[2]*a[i])
            if not new_k in dp[i+1]:
                dp[i+1][new_k] = 0
            dp[i+1][new_k] += dp[i][k]
    for k in dp[i+1]:
        dp[i+1][k] %= MOD
    

# print(a)

# for i in range(N+1):
#     print(dp[i])

sumv = 0
for k in dp[N]:
    if check(*k):
        sumv += dp[N][k]
sumv %= MOD
print(sumv)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
mod = 998244353
# DP ナップサックぽいやつ
# DP[i][j] := a_0からa_iまでの部分集合で和がjになるものの個数
# 配るDPの方が場合分けがなくて簡潔に書ける 計算量増えるかも
# DP[i-1][j]→DP[i][j]とDP[i][j + a_i ]に配る

aaa = [int(input()) for _ in range(N)]
sum_aaa = sum(aaa)

sum_now = 0
DP = [[0] * (sum_aaa+1) for i in range(N)]
DP2 = [[0] * (sum_aaa+1) for i in range(N)]

a = aaa[0]
DP[0][0] = 2
DP[0][a] = 1

DP2[0][0] = 1
DP2[0][a] = 1

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 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

		while (DP[i][j] > mod):
			DP[i][j] -= mod

	for j in range(min(sum_now + 1, int(sum_aaa /2)+1)):
		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

		while (DP2[i][j] > mod):
			DP2[i][j] -= mod

# print(DP2)
minimum_invalid_length = int((sum_now+1)//2)
num_too_long = sum (DP[N-1][minimum_invalid_length:])
if (sum_aaa %2 == 0):
	num_too_long -= DP2[N-1][int(sum_aaa /2)]
# print(num_too_long)
# print(sum(aaa))
print((3** N - num_too_long * 3) % mod )

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from pprint import pprint

MOD = 998244353  # type: int

def solve(N: int, a: "List[int]"):
    s = sum(a)
    dp = [[[0] * 2 for _ in range(s + 1)] for _ in range(N + 1)] # dp[idx][sum][]
    dp[0][0][0] = 1
    dp[0][0][1] = 1
    for i in range(N):
        for j in range(s + 1):
            if j + a[i] <= s:
                dp[i + 1][j + a[i]][0] += dp[i][j][0]
                dp[i + 1][j + a[i]][1] += dp[i][j][1]
            dp[i + 1][j][0] += dp[i][j][0]
            dp[i + 1][j][1] += dp[i][j][1] * 2

    tmp = 0
    border = (s + 1) // 2
    uniq = 0
    #pprint(dp)
    for j in range(border, s + 1):
        tmp += dp[N][j][1]
        uniq += dp[N][j][0]
    #print(tmp, uniq)
    tmp -= uniq * 2
    tmp *= 3

    ret = (3 ** N) % MOD
    col_2 = (2 ** N) % MOD
    ret -= 3 + (col_2 - 2) * 3 + 3
    #print(ret)
    #for i in range(N):
    #    ret *= 3
    #    ret %= MOD
    #    col_2 *= 2
    #    col_2 %= MOD
    ret -= tmp
    print(ret % MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(N) ]  # type: "List[int]"
    solve(N, a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort(reverse=True)
S = sum(A)

D = dict()


def f(i, r, g, b):
    if (i, r, g, b) in D.keys():
        return D[(i, r, g, b)]

    if max([r, g, b]) * 2 >= S:
        D[(i, r, g, b)] = 0
        return 0

    if i == N:
        D[(i, r, g, b)] = 1
        return 1

    D[(i, r, g, b)] = 0
    D[(i, r, g, b)] += f(i+1, r+A[i], g, b)
    D[(i, r, g, b)] += f(i+1, r, g+A[i], b)
    D[(i, r, g, b)] += f(i+1, r, g, b+A[i])

    return D[(i, r, g, b)] % 998244353

print(f(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

dic = {}
for n in range(N):
    a = int(input())
    if len(dic) == 0:
        r = (a, 0, 0)
        dic[r] = 1
        g = (0, a, 0)
        dic[g] = 1
        b = (0, 0, a)
        dic[b] = 1
    else:
        newdic = {}
        for k, v in dic.items():
            r = (k[0] + a, k[1], k[2])
            if r in newdic:
                newdic[r] = newdic[r] + v
            else:
                newdic[r] = v
            g = (k[0], k[1] + a, k[2])
            if g in newdic:
                newdic[g] = newdic[g] + v
            else:
                newdic[g] = v
            b = (k[0], k[1], k[2] + a)
            if b in newdic:
                newdic[b] = newdic[b] + v
            else:
                newdic[b] = v
        dic = newdic

tori = 0
for k, v in dic.items():
    if k[0] < k[1] + k[2] and k[1] < k[2] + k[0] and k[2] < k[0] + k[1]:
        tori = tori + v

print(tori % 998244353)

Submission status: Time Limit Exceeded

Solution code:
def mm(k,s1,s2,s3):
	if(len(k) == 1):
		if(s1 == k[0] or s2 == k[0] or s3 == k[0]):
			return 1
		else:
			return 0
	else:
		t = 0
		if(k[0] <= s1):
			t += mm(k[1:],s1-k[0],s2,s3)
		if(k[0] <= s2):
			t += mm(k[1:],s1,s2-k[0],s3)
		if(k[0] <= s3):
			t += mm(k[1:],s1,s2,s3-k[0])
		return t

N = input()
a = []
for i in range(N):
    a.append(input())
a.sort(reverse=True)
count = 0
suma = sum(a)
for i in range(suma-suma*2/3,suma-(suma/2)):
	for j in range(suma-i-(suma-i)/2,i+1):
		temp = mm(a,i,j,suma-i-j)
		if(i == j or j == suma-i-j):
			if(i == suma-i-j):
				count += temp
			else:
				count += temp*3
		else:
			count += temp*6
print(count)