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 itertools import combinations

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

indices = set(range(len(A)))
A_length = len(A)

count = 0
for a_n in range(1, A_length-1):
    for a_t in combinations(indices, a_n):
        for b_n in range(1, A_length-a_n):
            for b_t in combinations(indices-set(a_t), b_n):
                for c_t in combinations(indices-set(a_t)-set(b_t), A_length-a_n-b_n):
                    a = sum([A[i] for i in a_t])
                    b = sum([A[i] for i in b_t])
                    c = sum([A[i] for i in c_t])
                    if (a+b)>c and (b+c)>a and (c+a)>b:
                        count += 1
                        count %= 998244353

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import numpy as np


MOD=998244353
N=int(input())
a=[int(input()) for i in range(N)]
a.sort(reverse=True)

A=sum(a)
M=math.ceil(A/2)  
x =[ [0 for j in range(M+1)] for i in range(N)]
x[0][0]=2
x[0][min(a[0],M)]=1

p=M-A+a[0]
q=a[0]
for i in range(1,N):
    p+=a[i]
    q+=a[i]
    for j in range(max(p,0),min(q,M)+1):
        if j==M:
            x[i][j]=sum(x[i-1][ max(M-a[i],0): M ])+x[i-1][M]*3

        elif j-a[i]<0: x[i][j]=x[i-1][j]*2
        else: x[i][j]=x[i-1][j]*2+x[i-1][j-a[i]]

        x[i][j]%=MOD

if sum(a)%2==0:
    y =[ [0 for j in range(M+1)] for i in range(N)]
    y[0][0]=1
    p=M-A+a[0]
    q=a[0]
    for i in range(1,N):
        p+=a[i]
        q+=a[i]
        for j in range(max(p,0),min(q,M)+1):
            if j-a[i]<0: y[i][j]=y[i-1][j]
            else: y[i][j]=y[i-1][j]+y[i-1][j-a[i]]

            y[i][j]%=MOD

    ans=3**N-x[N-1][M]*3+y[N-1][M]*6



else: ans=3**N-x[N-1][M]*3
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

N = int(input())
LI = []
for a in range(N):
    LI.append(int(input()))

MOD = 998244353
SUM = sum(LI)

# dp[t][r]: t までの整数を塗り分けたときに赤にしたやつの和が r となる場合の数
dp = [[0 for _ in range(SUM + 1)] for _ in range(len(LI))]
dp[0][0] = 2  # 緑か青
dp[0][LI[0]] = 1
for t in range(1, len(LI)):
    for r in range(len(dp[t])):
        dp[t][r] += dp[t - 1][r] * 2 % MOD
        dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0

# 選び方の組み合わせ数
ans = (3 ** len(LI)) % MOD
# 赤の合計が SUM / 2 以上だと三角形作れないので、選び方の合計から引く
# 緑と青が一番大きいケースも同じなので * 3
ans -= sum([dp[-1][r] for r in range(math.ceil(SUM / 2), SUM + 1)]) * 3
ans %= MOD

if SUM % 2 == 0:
    # r == g, b == 0 のケースを重複して引いてるので足したい
    # dp[t][r]: t までの整数を赤と青だけで塗り分けたときに赤にしたやつの和が r となる場合の数
    dp = [[0 for _ in range(SUM // 2 + 1)] for _ in range(len(LI))]
    dp[0][0] = 1  # 青
    dp[0][LI[0]] = 1
    for t in range(1, len(LI)):
        for r in range(len(dp[t])):
            dp[t][r] += dp[t - 1][r] % MOD
            dp[t][r] += dp[t - 1][r - LI[t]] % MOD if 0 <= r - LI[t] <= len(dp[t - 1]) else 0
    # 赤緑、赤青、緑青
    ans += dp[-1][SUM // 2] * 3
    ans %= MOD

print(ans)

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:
import itertools


N = int(input())
A = [int(input()) for i in range(N)]
cnt = 0

idx = [i for i in range(3)]
idx_l = [idx for _ in range(N)]
ans = list(itertools.product(*idx_l))
for a in ans:
    first = 0
    second = 0
    third = 0
    if (len(set(a)) == 3):
        for i, v in enumerate(a):
            if v == 0:
                first += A[i]
            elif v == 1:
                second += A[i]
            else:
                third += A[i]
        path = [first, second, third]
        if 2 * max(path) < sum(path):
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



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

    dp = [defaultdict(int) for i in range(num)]

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2


    dp[0][0] = 2
    dp[0][data[0]] = 1

    dp2 = [defaultdict(int) for i in range(num)]
    dp2[0][0] = 1
    dp2[0][data[0]] = 1

    for i in range(1, num):
        now_num = data[i]
        for dic_num in dp[i-1].keys():
            dp[i][dic_num] += dp[i - 1][dic_num] * 2
            dp[i][dic_num+now_num] += dp[i - 1][dic_num]
            dp2[i][dic_num] += dp2[i - 1][dic_num]
            dp2[i][dic_num + now_num] += dp2[i - 1][dic_num]

    count = 0
    for i in dp[num-1].keys():
        if i >= max_length:
            count += dp[num - 1][i]


    count2 = 0
    for i in dp2[num - 1].keys():
        if i >= max_length:
            count2 += dp2[num - 1][i]

    zennbu = 3 ** num - 3*(2**num - 2) - 3
    hiku = 3 * (count - 2 * count2 + 1)
    ans = zennbu - hiku
    print(ans % 998244353)

    # print('-----')
    # print(sum_data)
    # print(max_length)
    # print(count, count2)
    # print(dp)
    # print(dp2)



if __name__ == '__main__':
    main()
    # print(300**300)

Submission status: Time Limit Exceeded

Solution code:

n = int( input() )

an = [0]*n

for i in range(n):
    an[i] = int(input())

an.sort(reverse = True)

total = sum(an)


def f(index, r, g, b):


    mmm = sorted([r,g,b]) 
    if index == n :
        return 0 if mmm[2] >= mmm[1] + mmm[0] else 1
      
    remain = total - sum(mmm)
    if mmm[2] -mmm[1] - mmm[0] >= remain:
        return 0

    if n < index :
        return 0

    v = an[index]
    
    t = 0
    t += f(index + 1, r + v, g    , b ) 
    t += f(index + 1, r    , g + v, b ) 
    t += f(index + 1, r    , g    , b + v ) 

    return t

v = an[0]
ans =  f(1,v,0,0)
ans += f(1,0,v,0)
ans += f(1,0,0,v)

mod = 998244353
print(ans % mod )

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



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

    dp = [defaultdict(int) for i in range(num)]

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2


    dp[0][0] = 2
    dp[0][data[0]] = 1

    for i in range(1, num):
        now_num = data[i]
        for dic_num in dp[i-1].keys():
            dp[i][dic_num] += dp[i - 1][dic_num] * 2
            dp[i][dic_num+now_num] += dp[i - 1][dic_num]

    count = 0
    for i in dp[num-1].keys():
        if i >= max_length:
            count += dp[num - 1][i]



    dp2 = [defaultdict(int) for i in range(num)]
    dp2[0][0] = 1
    dp2[0][data[0]] = 1

    for i in range(1, num):
        now_num = data[i]
        for dic_num in dp2[i - 1].keys():
            dp2[i][dic_num] += dp2[i - 1][dic_num]
            dp2[i][dic_num + now_num] += dp2[i - 1][dic_num]

    count2 = 0
    for i in dp2[num - 1].keys():
        if i >= max_length:
            count2 += dp2[num - 1][i]

    zennbu = 3 ** num - 3*(2**num - 2) - 3
    hiku = 3 * (count - 2 * count2 + 1)
    ans = zennbu - hiku
    print(ans % 998244353)

    # print('-----')
    # print(sum_data)
    # print(max_length)
    # print(count, count2)
    # print(dp)
    # print(dp2)



if __name__ == '__main__':
    main()
    # print(300**300)

Submission status: Time Limit Exceeded

Solution code:
import itertools


N = int(input())
A = [int(input()) for i in range(N)]
cnt = 0

idx = [i for i in range(3)]
idx_l = [idx for _ in range(N)]
ans = list(itertools.product(*idx_l))
for a in ans:
    first = 0
    second = 0
    third = 0
    if (len(set(a)) == 3):
        for i, v in enumerate(a):
            if v == 0:
                first += A[i]
            elif v == 1:
                second += A[i]
            else:
                third += A[i]
        path = [first, second, third]
        if 2 * max(path) < sum(path):
            cnt += 1
print(cnt)

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


ptn_num = 3 ** N - 3*(calc_bigger(0,0) - calc_eq_2(0,0))

print(ptn_num % 998244353)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

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

@lru_cache(maxsize = None)
def func(n, r, g, b):
    c = m - a[n]
    if n == N - 1:
        return (1 if r < c else 0) + (1 if g < c else 0) + (1 if b < c else 0)
    else:
        return ((func(n + 1, r + a[n], g, b) if r < c else 0) + (func(n + 1, r, g + a[n], b) if g < c else 0) + (func(n + 1, r, g, b + a[n]) if b < c else 0)) % 998244353


print(func(0, 0, 0, 0))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    mod=998244353
    N=int(input())
    A=[]
    for i in range(N):
        A.append(int(input()))
    su=sum(A)
    su2=su//2
    A.sort()
    csum=[0]*(N+1)
    for i in range(N):
        csum[i+1]=csum[i]+A[i]

    q=[]
    q.append((N-2,0,0,A[N-1]))
    b=[0]*3
    ans=0
    try:
        while True:
            i,b[0],b[1],b[2] = q.pop()
            b.sort()
            if i==0:
                if b[0]+b[1]+A[0]>b[2] and b[1]+b[2]>b[0]+A[0]:
                    ans+=1
                if b[0]+b[1]+A[0]>b[2] and b[0]+b[2]>b[1]+A[0]:
                    ans+=1
                if b[0]+b[1]>b[2]+A[0]:
                    ans+=1
                continue
            if i>=N-3:
                q.append((i-1,b[0],b[1],b[2]+A[i]))
                q.append((i-1,b[0],b[1]+A[i],b[2]))
                q.append((i-1,b[0]+A[i],b[1],b[2]))
                continue
            if b[0]+b[1]>b[2]+csum[i+1]:
                ans+=3**(i+1)
                ans%=mod
                continue
            if b[0]+b[1]+csum[i+1]<=b[2]:
                continue
            q.append((i-1,b[0],b[1],b[2]+A[i]))
            q.append((i-1,b[0],b[1]+A[i],b[2]))
            q.append((i-1,b[0]+A[i],b[1],b[2]))
    except IndexError:
        pass
    ans*=3
    ans%=mod
    return ans

print(solve())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

import sys
input = sys.stdin.readline

N = int(input())
A = []
for _ in range(N):
  A.append(int(input()))
A.sort()

cands = defaultdict(int)
cands[(0,0,0)] = 1
for a in A:
  next_dict = defaultdict(int)
  for (r,g,b),val in cands.items():
    next_dict[tuple(sorted((r+a, g, b)))] += val 
    next_dict[tuple(sorted((r, g+a, b)))] += val 
    next_dict[tuple(sorted((r, g, b+a)))] += val 
  cands = next_dict

cnt = 0
for key, val in cands.items():
  a, b, c = key
  if (a + b > c) and (b + c > a) and (c + a > b):
    cnt += val
    cnt %= 998244353
  
print(cnt)

Submission status: Time Limit Exceeded

Solution code:

def kari():
    N = list(map(int, input().split()))
    A, B = map(int, input().split())

ans_num = 0

# def check(a_sum, b_sum, data, max_length):
#     global ans_num
#     c_sum = sum(data)
#     if c_sum >= max_length:
#         return
#     ans_num += 1


def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



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

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2

    # print(sum_data, max_length)

    # check([data[0]], [], [], 1, data[1:], max_length, num, data[0], 0, 0)
    # check([], [data[0]], [], 1, data[1:], max_length, num, 0, data[0], 0)
    # check([], [], [data[0]], 1, data[1:], max_length, num, 0, 0, data[0])

    check(1, data, max_length, num, data[0], 0, 0)
    # check(1, data, max_length, num, 0, data[0], 0)
    # check(1, data, max_length, num, 0, 0, data[0])

    global ans_num
    print((ans_num * 3) % 998244353)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

goukei = sum(A)
A.sort()
A.reverse()


def f(lst, r, g, b, nokori, dic):
    if len(lst) == 0:
        hen = [r, g, b]
        hen.sort()
        if hen[0] == 0:
            return 0
        if hen[0] + hen[1] > hen[2]:
            return 1
        else:
            return 0

    hen = [r, g, b]
    hen.sort()
    if hen[0] + hen[1] + nokori < hen[2]:
        return 0

    rnitasita = 0
    gnitasita = 0
    bnitasita = 0
    if tuple([tuple(lst[1:]), r+lst[0], g, b]) in dic.keys():
        rnitasita = dic[tuple([tuple(lst[1:]), r+lst[0], g, b])]
    else:
        rnitasita = f(lst[1:], r+lst[0], g, b, nokori-lst[0], dic)
        dic[tuple([tuple(lst[1:]), r+lst[0], g, b])] = rnitasita

    if tuple([tuple(lst[1:]), r, g+lst[0], b]) in dic.keys():
        gnitasita = dic[tuple([tuple(lst[1:]), r, g+lst[0], b])]
    else:
        gnitasita = f(lst[1:], r, g+lst[0], b, nokori-lst[0], dic)
        dic[tuple([tuple(lst[1:]), r, g+lst[0], b])] = gnitasita

    if tuple([tuple(lst[1:]), r, g, b+lst[0]]) in dic.keys():
        bnitasita = dic[tuple([tuple(lst[1:]), r, g, b+lst[0]])]
    else:
        bnitasita = f(lst[1:], r, g, b+lst[0], nokori-lst[0], dic)
        dic[tuple([tuple(lst[1:]), r, g, b+lst[0]])] = bnitasita

    return rnitasita + gnitasita + bnitasita


print(f(A, 0, 0, 0, sum(A), {}) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
M=998244353
_n=int(input())
pdic={(0,0,0):1}
_a=[]
_a.sort(reverse=True)
for n in range(_n):
    _a.append(int(input()))
l2=(sum(_a)+1)//2
for n in range(_n):
    prevdic=pdic
    pdic={}
    a=_a[n]
    for p,v in prevdic.items():
        for d in [(a,0,0),(0,a,0),(0,0,a)]:
            np=(p[0]+d[0],p[1]+d[1],p[2]+d[2])
            if np[0]>l2 or np[1]>l2 or np[2]>l2:
                continue
            if np not in pdic:
                pdic[np]=0
            pdic[np]+=v
            pdic[np]%=M
c=0
for p,v in pdic.items():
    if p[0]<p[1]+p[2] and p[1]<p[2]+p[0] and p[2]<p[0]+p[1]:
        c+=v
        c%=M
print(c%M)

Submission status: Time Limit Exceeded

Solution code:

def kari():
    N = list(map(int, input().split()))
    A, B = map(int, input().split())

ans_num = 0

# def check(a_sum, b_sum, data, max_length):
#     global ans_num
#     c_sum = sum(data)
#     if c_sum >= max_length:
#         return
#     ans_num += 1


def serch(data, a_sum, max_length, num):
    b_sum = 0
    for i in range(len(data) - 1):
        b_sum += data[i]
        if b_sum >= max_length:
            break
        check(a_sum, b_sum, data[i + 1:], max_length)

def final_check(a_sum, b_sum, c_sum, max_length):
    global ans_num
    if a_sum == 0 or b_sum == 0 or c_sum == 0:
        return
    if a_sum < max_length and b_sum < max_length and c_sum < max_length:
        ans_num += 1


    # print(ans_num)

def check(nex_ind, data, max_length, num, a_sum, b_sum, c_sum):
    if nex_ind >= num:
        final_check(a_sum, b_sum, c_sum, max_length)
        return

    now_point = data[nex_ind]

    a_sum += now_point

    if a_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    a_sum -= now_point

    b_sum += now_point
    if b_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    b_sum -= now_point

    c_sum += now_point
    if c_sum >= max_length:
        pass
    else:
        check(nex_ind + 1, data, max_length, num, a_sum, b_sum, c_sum)
    c_sum -= now_point



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

    if sum_data % 2 == 0:
        max_length = sum_data // 2
    else:
        max_length = (sum_data + 1) // 2

    # print(sum_data, max_length)

    # check([data[0]], [], [], 1, data[1:], max_length, num, data[0], 0, 0)
    # check([], [data[0]], [], 1, data[1:], max_length, num, 0, data[0], 0)
    # check([], [], [data[0]], 1, data[1:], max_length, num, 0, 0, data[0])

    check(1, data, max_length, num, data[0], 0, 0)
    check(1, data, max_length, num, 0, data[0], 0)
    check(1, data, max_length, num, 0, 0, data[0])

    global ans_num
    print(ans_num % 998244353)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#D - Three Colors
n = int(input())
a=[]
memo = []
for i in range(n):
    a.append(int(input()))
def isTriangle(R,G,B):
    rgb = sorted([R,G,B])
    if (rgb[2]-rgb[1] < rgb[0]) and (rgb[2] < rgb[0] + rgb[1]) and (R*G*B != 0 ) and (R+G+B == sum(rgb[:])):
        return True
    else:
        return False
    
def select(R, G, B, List):
    if len(List) == 0:
        if isTriangle(R, G, B):
            return 1
        else:
            return 0
    else:
        return select(R+List[0], G, B, List[1:])+select(R, G+List[0], B, List[1:])+select(R, G, B+List[0], List[1:])
print(select(0,0,0,a)%998244353)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
# import math
import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = stdin.readline().rstrip().split()[0]

N = int(stdin.readline().rstrip().split()[0])
A=[]
for i in range(N):
  A.append(int(stdin.readline().rstrip().split()[0]))

MOD = 998244353
A.sort()
cumsum = np.cumsum(A)
A=A[::-1]

def tri(RGB):
  R,G,B=RGB
  arr = [R,G,B]
  arr.sort()
  if arr[2]<arr[0]+arr[1]:
    return 1
  else:
    return 0

DP_memo = {}
DP_memo[0] = {}
def DP(RGB,n):
  R,G,B = RGB
  arr = [R,G,B]
  arr.sort()
  RGB = tuple(arr)
  if n in DP_memo:
    if RGB in DP_memo[n]:
      return DP_memo[n][RGB]
  else:
    DP_memo[n] = {}

  if n==N:
    return tri(RGB)
  if B-(R+G+cumsum[N-n-1])>=0:
    if n+1 in DP_memo:
      DP_memo[n][RGB]=0
    else:
      DP_memo[n]={}
      DP_memo[n][RGB]=0
    return 0
  
  ret = 0
  ret += DP((R+A[n],G,B),n+1)
  ret += DP((R,G+A[n],B),n+1)
  ret += DP((R,G,B+A[n]),n+1)
  if n+1 in DP_memo:
    DP_memo[n][RGB]=ret
  else:
    DP_memo[n]={}
    DP_memo[n][RGB]=ret
  return ret
  
  

ans=DP((0,0,0), 0)
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a=[]
for _ in [0]*n:
    a.append(int(input()))
a_all=sum(a)
a=sorted(a,reverse=True)
d={}
def an(i,r,g,b):
    if r>=a_all/2 or g>=a_all/2 or b>=a_all/2 :
        return 0
    if i==n:
        return 1
    else:
        key="*".join([str(x) for x in (i,r,g,b)])
        if key not in d.keys():
            d[key]=an(i+1,r+a[i],g,b)+an(i+1,r,g+a[i],b)+an(i+1,r,g,b+a[i])
        return d[key]
    
ans=an(0,0,0,0)
print(ans%998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        ret = 1 if c < a + b else 0
        memo[(a, b, c)] = ret
        return ret
    if total < (2 * c):
        ret = 0
        memo[(a, b, c)] = ret
        return ret
    if (a, b, c) in memo:
        return memo[(a, b, c)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(v0[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

    memo[(a, b, c)] = ret
    return ret

print(dfs(0, 0, 0, 0))

Submission status: Time Limit Exceeded

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

nList.sort()
#三角形が存在する条件：最長辺が、残り2辺の合計未満である

#絶対TLEするけど記念にパピコしたい
kouho = []
def dfs(idx, a, b, c, at):
    if max(a,b,c) > a+b+c - max(a,b,c) + at:
        # 長辺が長すぎるので終わる
        return
    if idx == N:
        if a > 0 and b > 0 and c > 0:
            if max(a,b,c) < a+b+c - max(a,b,c):
                kouho.append((a,b,c))
        return
    re1 = dfs(idx+1, a+nList[idx], b, c, at-nList[idx])
    re2 = dfs(idx+1, a, b+nList[idx], c, at-nList[idx])
    re3 = dfs(idx+1, a, b, c+nList[idx], at-nList[idx])

dfs(0,0,0,0,sum(nList))
print((len(kouho)%998244353))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N = int(input())

a = []

for _ in range(N):
    a.append(int(input()))


@lru_cache(maxsize=None)
def rec(i, R, G, B):

    if i == N:
        if R < G + B and G < R + B and B < R + G:
            return 1
        else:
            return 0

    a_sum = rec(i + 1, R + a[i], G, B)
    b_sum = rec(i + 1, R, G + a[i], B)
    c_sum = rec(i + 1, R, G, B + a[i])

    return a_sum + b_sum + c_sum


print(rec(0, 0, 0, 0) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import copy
N = int(input())

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

MOD = 998244353
scores = []
scores.append([0, 0, 0])

for a in A:
    new_scores = []
    for score in scores:
        #a
        for index in range(3):
            one_score = copy.deepcopy(score)
            one_score[index] += a
            new_scores.append(one_score)
    scores = new_scores

# 3核の成立

count = 0
for a, b, c in scores:
    if a >= b +c:
        continue
    if b >= c + a:
        continue
    if c >= a + b:
        continue

    count += 1
    count %= MOD

print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
memo = dict()

def tc(a, n, i, r, g, b, t):
    m = max(r, g, b)
    if t - m <= m:
        return 0

    if i < n:

        _r, _g, _b = sorted([r, g, b])
        if (i, _r, _g, _b, t) in memo:
            return memo[(i, _r, _g, _b, t)]
        else:
            tmp = tc(a, n, i+1, r+a[i], g, b, t) \
                + tc(a, n, i+1, r, g+a[i], b, t) \
                + tc(a, n, i+1, r, g, b+a[i], t)
            memo[(i, _r, _g, _b, t)] = tmp
            return tmp
    else:
        if (r + g) > b and (r + b) > g and (g + b) > r:
            return 1
        else:
            return 0


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

a.sort(reverse=True)
total = sum(a)

print(tc(a, n, 0, 0, 0, 0, total) % 998244353)

Submission status: Time Limit Exceeded

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

state = {(0,0):1}
total = sum(a)

for s in a:
    new_state = {}
    for x, j in state.items():
        if x[0]>total//2 or x[1]>total//2:
            continue
        for v in ((1,0), (0,1)):
            n = tuple(sorted((s*v[0]+x[0], s*v[1]+x[1])))
            if not n in new_state:
                new_state[n] = j
            else:
                new_state[n] = (new_state[n]+j)%998244353
        if not x in new_state:                
            new_state[x] = j
        else:
            new_state[x] = (new_state[x]+j)%998244353
    new_state, state = state, new_state

ans = 0

for x, j in state.items():
    c = total-x[0]-x[1]
    if x[0]!=0 and x[1]!=0 and c!=0\
       and x[0]<x[1]+c\
       and x[1]<x[0]+c\
       and c<x[0]+x[1]: 
        ans = (ans+j)%998244353

print(ans)

Submission status: Time Limit Exceeded

Solution code:
cou = 0
def go(l,a,b,c,i):
	global cou
	if i == len(l):
		if (a+b+c) - max(a,b,c) > max(a,b,c):
			cou += 1 

	else:
		go(l,a+l[i],b,c,i+1)
		go(l,a,b+l[i],c,i+1)
		go(l,a,b,c+l[i],i+1)


n = int(input())
a = []
for i in range(n):
	a.append(int(input()))
go(a,0,0,0,0)

print(cou)

Submission status: Time Limit Exceeded

Solution code:
M=998244353
_n=int(input())
pdic={(0,0,0):1}
_a=[]
for n in range(_n):
    _a.append(int(input()))
l2=(sum(_a)+1)//2
for n in range(_n):
    prevdic=pdic
    pdic={}
    a=_a[n]
    for p,v in prevdic.items():
        for d in [(a,0,0),(0,a,0),(0,0,a)]:
            np=(p[0]+d[0],p[1]+d[1],p[2]+d[2])
            if np[0]>l2 or np[1]>l2 or np[2]>l2:
                continue
            if np not in pdic:
                pdic[np]=0
            pdic[np]+=v
            pdic[np]%=M
c=0
for p,v in pdic.items():
    if p[0]<p[1]+p[2] and p[1]<p[2]+p[0] and p[2]<p[0]+p[1]:
        c+=v
        c%=M
print(c)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

N = int(input())

a = []

for _ in range(N):
    a.append(int(input()))


@lru_cache()
def rec(i, R, G, B):

    if i == N:
        if R < G + B and G < R + B and B < R + G:
            return 1
        else:
            return 0

    a_sum = rec(i + 1, R + a[i], G, B)
    b_sum = rec(i + 1, R, G + a[i], B)
    c_sum = rec(i + 1, R, G, B + a[i])

    return a_sum + b_sum + c_sum


print(rec(0, 0, 0, 0) % 998244353)

Submission status: Time Limit Exceeded

Solution code:
M=998244353
_n=int(input())
pdic={(0,0,0):1}
for n in range(_n):
    prevdic=pdic
    pdic={}
    a=int(input())
    for p,v in prevdic.items():
        for d in [(a,0,0),(0,a,0),(0,0,a)]:
            np=(p[0]+d[0],p[1]+d[1],p[2]+d[2])
            if np not in pdic:
                pdic[np]=0
            pdic[np]+=v
            pdic[np]%=M
c=0
for p,v in pdic.items():
    if p[0]<p[1]+p[2] and p[1]<p[2]+p[0] and p[2]<p[0]+p[1]:
        c+=v
        c%=M
print(c)

Submission status: Time Limit Exceeded

Solution code:
import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

n = readInt()
aa = []
for i in range(n):
    aa.append(readInt())

memo = {}
def dfs(a, b, c, i):
    if i == len(aa):
        return 1 if c < a + b else 0
    if (a, b, c) in memo:
        return memo[(a, b, c)]

    ret = 0
    v0 = sorted([a + aa[i], b, c])
    ret = (ret + dfs(v0[0], v0[1], v0[2], i + 1)) % 998244353

    v1 = sorted([a, b + aa[i], c])
    ret = (ret + dfs(v1[0], v1[1], v1[2], i + 1)) % 998244353

    v2 = sorted([a, b, c + aa[i]])
    ret = (ret + dfs(v2[0], v2[1], v2[2], i + 1)) % 998244353

    memo[(a, b, c)] = ret
    return ret

print(dfs(0, 0, 0, 0))