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:
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(1)

Submission status: Wrong Answer

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

n = int(input())
a = tuple([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(1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
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)]
dp = np.zeros((n, w+1))
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 = np.zeros((n, s+1))
    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(int(res))

Submission status: Wrong Answer

Solution code:
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)

Submission status: Wrong Answer

Solution code:
N = int(input())
DIV = 998244353
L = 180010

dp = [[0] * L for i in range(N+1)]
dp[0][0] = 1
  
for i in range(N):
    a = int(input())
    for j in range(L):
        dp[i+1][j] = dp[i][(j-a)%L] + dp[i][(j+a)%L] * 2
        

        
st = 0
for i in range(L//2):
    st += dp[N][i]
    


ans = (3**N - st*3 + dp[N][0]//3) %DIV
print(ans)

Submission status: Wrong Answer

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

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

dp = [[0]*(90002) for i in range(n)]


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

w = sum(a)
#sより大きいのはブー
if w %2 == 0:
    s = w//2+1
else:
    s = w//2
cnt = 0
for i in range(s+1,90001):
    cnt += dp[-1][i]
    cnt = cnt%mod


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

Submission status: Wrong Answer

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

MOD = 998244353

a.sort()
su = sum(a)
bor = su // 2 + su % 2

P = [1] * (N + 1)
for i in range(1, N + 1):
  P[i] = P[i - 1] * 2 % MOD

TP = [1] * (N + 1)
for i in range(1, N + 1):
  TP[i] = TP[i - 1] * 3 % MOD

def cal(x, y, z):
  if y == 0:
    k = TP[z] - (P[z] * 2) - 3
  elif y == 1:
    k = 2 * (TP[z] - P[z] - 2)
  else:
    k = (P[y] - 2) * TP[z]
    if z > 1:
      k += 2 * (TP[z] - P[z] - 2)
    elif z == 1:
      k += 2
  if k < 0:
    k += MOD
  return k % MOD
  
def getAns(num, y, z):
  if y == N:
    return 0
  ans = 0
  if num + a[y] >= bor:
    if N - z - 1 > 1:
      ans += cal(z + 1, y - z, N - y - 1)
  else:
    ans += getAns(num + a[y], y + 1, z + 1) % MOD
  ans += getAns(num, y + 1, z) % MOD
  return ans

ans = getAns(0, 0, 0)

all = 1
for i in range(N):
  all = all * 3 % MOD
all -= P[N] * 3 + 3
ans = all - ans

while ans < 0:
  ans += MOD

print(ans % MOD)

Submission status: Wrong Answer

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

    rest = S - sum([r, g, b])
    if rest + b < g:
        D[(i, r, g, b)] = 0
        return 0

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

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

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

    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) * 3) % 998244353)

Submission status: Wrong Answer

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

    rest = S - sum([r, g, b])
    if rest + b < g:
        D[(i, r, g, b)] = 0
        return 0

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

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

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

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

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

print((f(0, 0, 0, 0) * 3) % 998244353)

Submission status: Wrong Answer

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.roll(dp[i-1], A[i]) + dp[i-1]*2
  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: Wrong Answer

Solution code:
from collections import defaultdict

MOD = 998244353


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()

s = s.rstrip('#')
s = s.lstrip('.')

if len(set(s)) <= 1:
    print(0)
    exit(0)

print(min(s.count('#'), s.count('.')))

Submission status: Wrong Answer

Solution code:
N = int(input())
DIV = 998244353
L = 180010

dp = [[0] * L for i in range(N+1)]
dp[0][0] = 1
  
for i in range(N):
    a = int(input())
    for j in range(L):
        dp[i+1][j] = dp[i][(j-a)%L] + dp[i][(j+a)%L] * 2
        

        
st = 0
for i in range(L//2):
    st += dp[N][i]
    


ans = (3**N - st*3 + dp[N][0]//3) %DIV
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# coding: utf-8


def main():
    n = int(input())
    s = input()
    lw = 0
    for i in range(len(s)):
        if s[i] == '#':
            break
        lw += 1
    rb = len(s)
    for i in range(len(s)):
        if s[len(s)-i-1] == '.':
            break
        rb -= 1
    w = sum(1 for c in s[lw:rb] if c == '.')
    b = len(s[lw:rb]) - w
    best = w
    flag = True
    db = 0
    dw = 0
    for i, c in enumerate(s[lw:rb]):
        if flag and c == '#':
            db += 1
            continue
        flag = False
        if c == '.':
            dw += 1
            continue
        best = min(best, w-dw+db)
        flag = True
    print(best)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


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

S = sum(A)
L = S//2
dp1 = [0]*(L+1)
dp2 = [0]*(L+1)
dp1[0] = 1
dp2[0] = 1
for a in A:
    for i in reversed(range(L-a+1)):
        dp1[i+a] = (dp1[i+a] + dp1[i])%mod
        dp2[i+a] = (dp2[i+a] + dp2[i]*2)%mod

p1 = 0
p2 = 0
for s in range(1,L+1):
    p1 = (p1 + dp1[s]*6)%mod
    p2 = (p2 + dp2[s]*3)%mod
ans = (pow(3, N, mod) + 3 - 3*pow(2, N, mod) - p2 + p1) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
P = 998244353
A = [int(input()) for _ in range(N)]
s = sum(A)

def calc(m):
    X = [1] + [0] * s
    for a in A:
        for i in range(a, s+1)[::-1]:
            X[i] = (X[i] + X[i-a] * m) % P
    return X

Y = calc(2)
ans = sum([Y[i] for i in range(s//2+1)]) + (0 if s%2 else -calc(1)[s//2])
print((pow(3, N, P) - ans*3) % P)

Submission status: Time Limit Exceeded

Solution code:
mod=998244353 

N=int(input())
alist=[]
all_num=1
for i in range(N):
  alist.append(int(input()))
  all_num *= 3
  all_num %= mod
  
asum=sum(alist)
#print(alist)
#print(all_num)

dp=[]
dp2=[]
for _ in range(N+1):
  dp.append([0]*(asum+1))
  dp2.append([0]*(asum+1))
  
dp[0][0]=1
dp2[0][0]=1
#print(dp)
for i in range(N):
  a=alist[i]
  for j in range(asum):
    dp[i+1][j] += 2*dp[i][j]
    dp[i+1][j] %= mod
    dp2[i+1][j] += dp2[i][j]
    dp2[i+1][j] %= mod
    if dp[i][j] > 0:
      dp[i+1][j+a] += dp[i][j]
      dp[i+1][j+a] %= mod
      dp2[i+1][j+a] += dp2[i][j]
      dp2[i+1][j+a] %= mod
    
#print(dp)
#print(dp2)

invalid_num = sum(dp[N][(asum+1)//2:])%mod 
#print(invalid_num)

if asum%2 == 0:
  print((all_num-3*invalid_num+3*dp2[N][asum//2])%mod)
else:
  print((all_num-3*invalid_num)%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
def pow(n,k,m):#n^k mod m
    ans = 1
    while k>0:
        if(k & 1):ans = (ans*n) % m
        n = (n*n)%m
        k >>= 1
    return ans

n = int(input())
a =[int(input()) for i in range(n)]
s = sum(a)
dp1 = [0 for i in range(s+1)] #dp1[x]:Bの和=xとなるような塗り方の総数

dp1[0] = 1

for i in range(n):
    dpp1 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:dpp1[j+a[i]] = (dp1[j]+dpp1[j+a[i]]) % MOD
        dpp1[j] = (dp1[j]*2 + dpp1[j]) % MOD
    dp1 = dpp1[:]

if s % 2 == 1:
    ans1 = sum(dp1[(s//2) + 1:]) % MOD
    print((pow(3,n,MOD)-ans1*3) % MOD)
    exit()

ans1 = sum(dp1[(s//2):]) % MOD

dp2 = [0 for i in range(s+1)]

dp2[0] = 1

for i in range(n):
    dpp2 = [0 for i in range(s+1)]
    for j in range(s+1):
        if j+a[i] <= s:dpp2[j+a[i]] = (dp2[j]+dpp2[j+a[i]]) % MOD
        dpp2[j] = (dp2[j] + dpp2[j]) % MOD
    dp2 = dpp2[:]

print((pow(3,n,MOD)-(ans1*3 - dp2[s//2]*3)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache


N = int(input())
As = list()
for i in range(N):
    As.append(int(input()))

MOD = 998244353
S = sum(As)

base = 3 ** N % MOD

# R >= S/2, N
@lru_cache(maxsize=None)
def larger_than_T(T, k):
    """equal to or larger than T in As[:k]
    """
    if k == 0:
        if T <= 0:
            return 1
        else:
            return 0
    # assign As[k-1] to G or B 
    return 2 * larger_than_T(T, k - 1) + larger_than_T(T - As[k-1], k - 1)

# R = G = S/2, N
@lru_cache(maxsize=None)
def equal_to_Ts(T1, T2, k):
    """R and G are equal to T1 and T2 respectively in As[:k].
    """
    if T1 < 0 or T2 < 0:
        return 0
 
    if k == 0:
        if T1 == 0 and T2 == 0:
            return 1
        else:
            return 0
    return equal_to_Ts(T1, T2, k - 1) + equal_to_Ts(T1 - As[k-1], T2, k - 1) + equal_to_Ts(T1, T2 - As[k-1], k - 1)

single = larger_than_T(S/2, N) % MOD
if S % 2 == 0:
    double = equal_to_Ts(S//2, S//2, N) % MOD
else:
    double = 0

# print(base, single, double)
ans = base - single * 3 + double * 3
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

a.sort(reverse=True)
sol = 3 ** n % modulo
s = sum(a)
half_s = s / 2


dp = [Counter([0])]
for i, ai in enumerate(a):
    dp.append(dp[i] + dp[i])
    for key, item in dp[-2].items():
        dp[-1][key + ai] += dp[-2][key]
        # if dp[-1][key + ai] > modulo:
        #    dp[-1][key + ai] -= modulo

sol -= 3 * sum(item for key, item in dp[-1].items() if key >= half_s)

if s % 2 == 0:
    dp = [Counter([0])]
    for i, ai in enumerate(a):
        dp.append(dp[-1].copy())
        for key, item in dp[-2].items():
            new_key = key + ai
            if new_key <= int(half_s):
                dp[-1][new_key] += dp[-2][key]
                # if dp[-1][new_key] > modulo:
                #    dp[-1][new_key] -= modulo

    sol += 3 * dp[-1][half_s]
sol %= modulo

print(sol)
# print(dp[-1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

a.sort(reverse=True)
sol = 3 ** n % modulo
s = sum(a)
half_s = s / 2

from collections import Counter
dp = [Counter([0])]
for i, ai in enumerate(a):
    dp.append(dp[i] + dp[i])
    for key, item in dp[-2].items():
        dp[-1][key + ai] += dp[-2][key]
        if dp[-1][key + ai] > modulo:
            dp[-1][key + ai]-=modulo

sol -= 3 * sum(item for key, item in dp[-1].items() if key >= half_s)

if s % 2 == 0:
    dp = [Counter([0])]
    for i, ai in enumerate(a):
        dp.append(dp[-1].copy())
        for key, item in dp[-2].items():
            new_key = key + ai
            if new_key <= int(half_s):
                dp[-1][new_key] += dp[-2][key]
                if dp[-1][new_key] > modulo:
                    dp[-1][new_key] -= modulo

    sol += 3 * dp[-1][half_s]
sol %= modulo

print(sol)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

sol = 3 ** n % modulo
s = sum(a)

from collections import Counter
dp = [Counter([0])]
for i, ai in enumerate(a):
    dp.append(dp[i] + dp[i])
    for key, item in dp[-2].items():
        dp[-1][key + ai] += dp[-2][key]


for key, item in dp[-1].items():
    if key >= s / 2:
        sol -= 3 * item

sol %= modulo

if s % 2 == 0:
    dp = [Counter([0])]
    for i, ai in enumerate(a):
        dp.append(dp[i].copy())
        for key, item in dp[-2].items():
            dp[-1][key + ai] += dp[-2][key]

    sol += 3*dp[-1][s //2]
    sol %= modulo

print(sol)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = [int(input()) for _ in range(n)]
modulo = 998244353

s = sum(a)

dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1

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

        if dp[i + 1][j] > modulo:
            dp[i + 1][j] -= modulo
sol = 3 ** n - 3 * sum(dp[-1][int((s + 1) / 2) :])


if s % 2 == 0:
    dp = [[0] * (s + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    cumsum = 0
    for i in range(n):
        cumsum += a[i]
        for j in range(cumsum + 1):
            dp[i + 1][j] = dp[i][j]
            if j - a[i] >= 0:
                dp[i + 1][j] += dp[i][j - a[i]]

            if dp[i + 1][j] > modulo:
                dp[i + 1][j] -= modulo

    sol += 3 * dp[-1][s // 2]
sol %= modulo

print(sol)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil

n = int(input())
a = [int(input()) for _ in range(n)]
s = sum(a)
modulo = 998244353

dp = [[0] * (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
        if j - a[i] >= 0:
            dp[i + 1][j] += dp[i][j - a[i]]

        if dp[i + 1][j] > modulo:
            dp[i + 1][j] -= modulo
sol = 3 ** n - 3 * sum(dp[-1][int((s + 1) / 2) :])


if s % 2 == 0:
    dp = [[0] * (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]
            if j - a[i] >= 0:
                dp[i + 1][j] += dp[i][j - a[i]]

            if dp[i + 1][j] > modulo:
                dp[i + 1][j] -= modulo

    sol += 3 * dp[-1][s // 2]
sol %= modulo

print(sol)

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

n = ni()
a = [ni() for _ in range(n)]

suma = sum(a)
MOD = 998244353

dp_rgb = [[0]*(suma+1) for _ in range(n+1)]
dp_gb = [[0]*(suma+1) for _ in range(n+1)]

dp_rgb[0][0] = 1
dp_gb[0][0] = 1

for i, ai in enumerate(a):
    for sm in range(suma+1):
        if sm + ai <= suma:
            dp_rgb[i+1][sm+ai] += dp_rgb[i][sm] % MOD
            dp_gb[i+1][sm+ai] += dp_gb[i][sm] % MOD
            
        dp_rgb[i+1][sm] += 2 * dp_rgb[i][sm] % MOD
        dp_gb[i+1][sm] += dp_gb[i][sm] % MOD
        
ng = 3 * sum(dp_rgb[n][-(-suma//2):]) % MOD
ok = 0 if suma%2 else 3*dp_gb[n][suma//2] % MOD

print((pow(3,n,MOD) - ng + ok) % MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for _ in range(N)]
A.sort()
MOD = 998244353

dp = [[0 for i in range(sum(A) + 1)] for j in range(2)] 
dp_half = [[0 for i in range(sum(A) + 1)] for j in range(2)]
dp[0][0] = 1
dp_half[0][0] = 1
for n in range(N):
    for i in range(sum(A) + 1):
        if i >= A[n]:
            dp[(n+1)%2][i] = (dp[n%2][i-A[n]] + dp[n%2][i] * 2) % MOD
            dp_half[(n+1)%2][i] = (dp_half[n%2][i-A[n]] + dp_half[n%2][i]) % MOD
        else:
            dp[(n+1)%2][i] = dp[n%2][i] * 2 % MOD
            dp_half[(n+1)%2][i] = dp_half[n%2][i]

if sum(A) % 2 == 0:
    dp[N%2][sum(A)//2] -= dp_half[N%2][sum(A) // 2]
print((3 ** N - sum(dp[N%2][(sum(A)+1)//2:]) * 3) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#   https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_d

class count_triungles():
    def __init__(self, remaining_number_lst):
        self.MAX_SIDE_LEN = int(sum(remaining_number_lst)/2) + sum(remaining_number_lst) % 2
        self.count_triungles = 0
        self.first_side_num_lst = []
        self.second_side_num_lst = []
        self.third_side_num_lst = []
        self.remaining_number_lst = remaining_number_lst
        self.s1_len = 0
        self.s2_len = 0
        self.s3_len = 0

    def can_established_triungle(self):
        if self.s1_len >= self.MAX_SIDE_LEN:
            return False
        elif self.s2_len >= self.MAX_SIDE_LEN:
            return False
        elif self.s3_len >= self.MAX_SIDE_LEN:
            return False
        return True

    def new_triangle_candidate_established(self):
        if len(self.remaining_number_lst) == 0:
            self.s1_len = sum(self.first_side_num_lst)
            self.s2_len = sum(self.second_side_num_lst)
            self.s3_len = sum(self.third_side_num_lst)
            """
            s1_lst = self.first_side_num_lst
            s2_lst = self.second_side_num_lst
            s3_lst = self.third_side_num_lst
            """
            if self.can_established_triungle():
#                print(self.first_side_num_lst, self.second_side_num_lst, self.third_side_num_lst)
                self.count_triungles += 1
                return True #   三角形が成り立ったとき
            return False    #   三角形が成り立たなかったとき
        return None         #   三角形が成り立つかどうか判断できない時

    def serach_new_triangle(self, side_num):    #   このメソッドは後でリファクタリング
        judge = self.new_triangle_candidate_established()
        if judge is not None:   #   三角形が成り立つかどうか判断できたとき
            return None

        tmp = self.remaining_number_lst.pop(0)
        if side_num == 1:
            self.first_side_num_lst.append(tmp)
            self.serach_new_triangle(side_num=1)
            self.serach_new_triangle(side_num=2)
            self.serach_new_triangle(side_num=3)
            self.first_side_num_lst.pop(-1)
        elif side_num == 2:
            self.second_side_num_lst.append(tmp)
            self.serach_new_triangle(side_num=1)
            self.serach_new_triangle(side_num=2)
            self.serach_new_triangle(side_num=3)
            self.second_side_num_lst.pop(-1)
        else:
            self.third_side_num_lst.append(tmp)
            self.serach_new_triangle(side_num=1)
            self.serach_new_triangle(side_num=2)
            self.serach_new_triangle(side_num=3)
            self.third_side_num_lst.pop(-1)
        self.remaining_number_lst.insert(0,tmp)

        return None

    def do_all_process(self):
        self.serach_new_triangle(side_num=1)
        self.serach_new_triangle(side_num=2)
        self.serach_new_triangle(side_num=3)
        return self.count_triungles


N = int(input())
remaining_number_lst = []
for i in range(N):
    remaining_number_lst.append(int(input()))

counter = count_triungles(remaining_number_lst)
count = counter.do_all_process()
"""
count *= 3  #   回転させる
count *= 2  #   裏返す
"""
count = int(count/3)
count %= 998244353
print(count)

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/2+1):
	allc = allc*9
	if(i*2 >= N):
		allc = allc/3
		k = a[i*2-1]
		for j in range(suma+1):
			if(j < k):
				dp[i][j] = dp[i-1][j]*2
				dp2[i][j] = dp2[i-1][j]
			else:
				dp[i][j] = dp[i-1][j]*2+dp[i-1][j-k]
				dp2[i][j] = dp2[i-1][j]+dp2[i-1][j-k]
	else:
		k = a[i*2-1]
		l = a[i*2]
		if(k<l):
			k,l = l,k
		for j in range(sum(a[:i*2+1])+1):
			if(j < l):
				dp[i][j] = dp[i-1][j]*4
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j]
			elif(j < k):
				dp[i][j] = dp[i-1][j]*4 + dp[i-1][j-l]*2
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j] + dp2[i-1][j-l]
			elif(j < k+l):
				dp[i][j] = dp[i-1][j]*4 + dp[i-1][j-l]*2 + dp[i-1][j-k]*2
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j] + dp2[i-1][j-l] + dp2[i-1][j-k]
			else:
				dp[i][j] = dp[i-1][j]*4+ dp[i-1][j-l]*2 + dp[i-1][j-k]*2 + dp[i-1][j-k-l]
				if(flag == 1):
					dp2[i][j] = dp2[i-1][j]+ dp2[i-1][j-l] + dp2[i-1][j-k] + dp2[i-1][j-k-l]
allc = allc - sum(dp[N/2][suma-suma/2:])*3
if(flag == 1):			
	allc += dp2[N/2][suma/2]*3
print(allc%DIV)

Submission status: Time Limit Exceeded

Solution code:
#
import random
import numpy as np
mod   = 998244353
n     = int(input())
a     = list(map(int, [input() for _ in range(n)])) #[random.randint(0,300) for _ in range(300)]

s2    = [0 for _ in range(301)]
s3    = [0 for _ in range(301)]
s2[2] = 1
s3[3] = 1 

# Số cách phân tập gồm i+1 p/tử thành 2 tập con ko rỗng
for i in range(3, 301):
    s2[i] = (1 + 2 * s2[i-1]) % mod 
    
# Số cách phân tập gồm i+1 p/tử thành 3 tập con ko rỗng    
for i in range(4, 301):
    s3[i] = (s2[i-1] + 3 * s3[i-1]) % mod

d1 = [0 for _ in range(90001)]
d2 = [0 for _ in range(90001)]

for x in a:
    for i in range(90000,-1,-1):
        if d2[i] > 0:
            d2[i+x] = (d2[i+x] + 2 * d2[i]) % mod
            
    for i in range(90000,-1,-1):
        if d1[i] > 0:
            d1[i+x]  = (d1[i+x] + d1[i]) % mod
            d2[i+x]  = (d2[i+x] + d1[i]) % mod
    d1[x] = (d1[x] + 1) % mod        
    #print(d1[:11])
S = sum(a)      
count = 0

for i in range(S // 2 +1):
    count += d2[i]
    
print(6*(s3[n]-count+mod) % mod)#20 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4

Submission status: Time Limit Exceeded

Solution code:
import math
import copy
import numpy as np

MOD = 998244353

n = int(input())
xxs = []
total = 0
for _ in range(n):
    t = int(input())
    xxs.append(t)
    total += t

xs = np.array(xxs)
dp = np.array([[0] * (total+1) for _ in range(n)])

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): # length of
    s = xs[i]
    curtotal += s
    dp[i] = (dp[i-1] * 2)
    for j in range (s,curtotal+1):
        if j - s >= 0:
            dp[i][j] = (dp[i][j] + dp[i-1][j-s])
    dp[i] %= MOD

plus = 0
if total % 2 == 0:
    dp2 = np.array([0] * (total // 2 + 1))
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        curtotal += s
        prev = copy.copy(dp2)
        for j in range(s,min(len(dp2), curtotal+1)):
            if j-s >= 0:
                dp2[j] =  (dp2[j] + prev[j-s]) % MOD
                #print(i,j,s,dp2)
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

MOD = 998244353

n = int(input())
xs = []
total = 0
for _ in range(n):
    t = int(input())
    xs.append(t)
    total += t

dp = [[0] * (total+1) for _ in range(n)]

dp[0][0] = 2
dp[0][xs[0]] = 1

curtotal = xs[0]
for i in range(1,n): # length of
    s = xs[i]
    curtotal += s
    for j in range (0,curtotal+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j - s >= 0:
            dp[i][j] = (dp[i][j] + dp[i-1][j-s]) % MOD


plus = 0
if total % 2 == 0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    curtotal = 0
    for i in range(n):
        s = xs[i]
        curtotal += s
        prev = copy.copy(dp2)
        for j in range(0,min(len(dp2), curtotal+1)):
            if j-s >= 0:
                dp2[j] =  (dp2[j] + prev[j-s]) % MOD
                #print(i,j,s,dp2)
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
import copy

MOD = 998244353

n = int(input())
xs = []
total = 0
for _ in range(n):
    t = int(input())
    xs.append(t)
    total += t

dp = [[0] * (total+1) for _ in range(n)]

dp[0][0] = 2
dp[0][xs[0]] = 1

for i in range(1,n): # length of
    s = xs[i]
    for j in range (0,total+1):
        dp[i][j] = (dp[i-1][j] * 2) % MOD
        if j - s >= 0:
            dp[i][j] = (dp[i][j] + dp[i-1][j-s]) % MOD

plus = 0
if total % 2 == 0:
    dp2 = [0] * (total // 2 + 1)
    dp2[0] = 1
    intotal = 0
    for i in range(n):
        s = xs[i]
        prev = copy.copy(dp2)
        for j in range(0,len(dp2)):
            if j-s >= 0:
                dp2[j] =  (dp2[j] + prev[j-s]) % MOD
                #print(i,j,s,dp2)
    plus = dp2[total//2]

#print(dp2)
minus = 0
for i in range(math.ceil(total/2), total+1):
    minus = (minus + dp[n-1][i]) % MOD


#print(3**n, minus, plus)
print(((3**n)%MOD - minus*3 + plus*3) % MOD)

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 = [[0]*(S+1) for _ in range(2)]
DP[0][0] = 2
DP[0][A[0]] = 1

# R=G=S/2, B=0
DP2 = [[0]*(S+1) for _ in range(2)]
DP2[0][0] = 1
DP2[0][A[0]] = 1


max_A = A[0]
for i in range(1, N):
    a = A[i]
    max_A += a
    curr_dp = DP[i % 2]
    prev_dp = DP[(i+1) % 2]
    curr_dp2 = DP2[i % 2]
    prev_dp2 = DP2[(i+1) % 2]
    for r in range(max_A+1):
        if r >= a:
            curr_dp[r] = prev_dp[r]*2 + prev_dp[r-a]
            curr_dp2[r] = prev_dp2[r] + prev_dp2[r-a]
        else:
            curr_dp[r] = prev_dp[r]*2
            curr_dp2[r] = prev_dp2[r]
#print(DP)
#print(DP2)

half_S = (S+1)//2
ans = (3**N) - 3*sum(DP[(N-1) % 2][half_S:])
if S % 2 == 0:
    ans += 3*DP2[(N-1) % 2][S//2]

print(ans % 998244353)