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:
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_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]
	for j in range(sum_now + 1):
		DP[i][j] += DP[i-1][j] * 2
		DP[i][j] %= mod
		DP[i][j + a] += DP[i-1][j]

		DP2[i][j] += DP2[i-1][j]
		DP2[i][j] %= mod
		DP2[i][j + a] += DP2[i-1][j]

	sum_now += a

# 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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    s = sum(a) / 2.0
    d = collections.defaultdict(int)
    d[(0,0)] = 1
    e = collections.defaultdict(int)
    nk = sum(a)
    ev = 0
    for c,i in zip(a[::-1],range(n)):
        for k,v in list(d.items()):
            if k[0] + nk < s:
                del d[k]
                continue
            t = k[0] + c
            kk = (t,k[1]+1)
            k1 = k[1] + 1
            if t >= s:
                kk = (i+1-k1,n-i-1)
                e[kk] += v
                if t == s:
                    ev += v
                    ev %= mod
                e[kk] %= mod
            else:
                d[kk] += v
                d[kk] %= mod
        nk -= c

    r = 0
    # print('s',s)
    for k,v in e.items():
        r += v * pow(2,k[0]) * pow(3,k[1]) * 3
        r %= mod
        # print('kvr', k,v,r)
    r -= ev * 3
    r %= mod
    # print(pow(3,n,mod), r)

    return (pow(3,n,mod) - r) % mod


print(main())

Submission status: Time Limit Exceeded

Solution code:

import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = [int(input()) for i in range(N)]
from functools import lru_cache

mod = 998244353
@lru_cache(maxsize=None)
def solve(i, s, m):
    if i==-1:
        if s==0 and m==0:
            return 1
        else:
            return 0
    if s<0 or m<0:
        return 0
    return (solve(i-1, s, m) + solve(i-1, s-A[i], m) + solve(i-1, s, m-A[i])) % mod

ans = 0
su = sum(A)
for sm in range(su//2+1, su*2//3+1):
    l = su - sm
    for s in range(max(1, su-l-l), sm//2+1):
        m = sm - s
        if not (s <= m <= l):
            #print("a")
            continue
        if s==m==l:
            mul = 1
        elif s==m or m==l:
            mul = 3
        else:
            mul = 6
        ans += solve(N-1, s, m) * mul
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    s = sum(a) / 2.0
    d = collections.defaultdict(int)
    d[(0,0)] = 1
    e = collections.defaultdict(int)
    nk = sum(a)
    for c,i in zip(a[::-1],range(n)):
        for k,v in list(d.items()):
            if k[0] + nk < s:
                del d[k]
                continue
            t = k[0] + c
            kk = (t,k[1]+1)
            k1 = k[1] + 1
            if t >= s:
                kk = (t==s,i+1-k1,n-i-1)
                e[kk] += v
                e[kk] %= mod
            else:
                d[kk] += v
                d[kk] %= mod
        nk -= c

    r = 0
    # print('s',s)
    for k,v in e.items():
        if k[0]:
            r += v * pow(2,k[1]) * pow(3,k[2]) * 3
            r -= v * 3
        else:
            r += v * pow(2,k[1]) * pow(3,k[2]) * 3
        r %= mod
        # print('kvr', k,v,r)
    # print(pow(3,n,mod), r)

    return (pow(3,n,mod) - r) % mod


print(main())

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

dp = [[0]*(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):
  for j in range(temp_sum+1):
    dp[i][j] = (dp[i][j]+ dp[i-1][j]*2) %mod
    dp[i][j+A[i]] = (dp[i][j+A[i]] + dp[i-1][j]) %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



print(answer)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

total = sum(a)
sup = (total - 1) // 2

# total > 2 * max(R,G,B)
# を満たすR,G,Bの場合の数
# (total - 1) // 2 >= max(R,G,B)

dp = [[[0 for _ in range(total + 1)] for _ in range(total + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1
# dp[i][R][G]:=i番目まででRGとなる総数

# 枝刈り
# sup = (total - 1) // 2
# sup >= max(R,G,B)
# supを超えるRGBはdp遷移時にカット

for i in range(N):
    # a[i]はRGBのいずれかに加算
    for s in range(2 * sup + 1):
        for r in range(min(s, sup) + 1):
            g = s - r
            if r - a[i] >= 0:
                dp[i + 1][r][g] += dp[i][r - a[i]][g]
                dp[i + 1][r][g] %= MOD
            if g - a[i] >= 0:
                dp[i + 1][r][g] += dp[i][r][g - a[i]]
                dp[i + 1][r][g] %= MOD
            dp[i + 1][r][g] += dp[i][r][g]
            dp[i + 1][r][g] %= MOD
            # Bに対応

ans = 0
for r in range(sup + 1):
    for g in range(sup + 1):
        if total - r - g > sup: continue
        ans += dp[N][r][g]
        ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MOD = 998244353
A = []
S = [0]
for i in range(N):
    A.append(int(input()))
    S.append(S[-1] + A[-1])
S = S[::-1]
A = sorted(A, reverse=True)
dp = [[] for i in range(N + 1)]
dp[0].append((0, 0, 0))
d = {}
d[(0, 0, 0)] = 1
for i in range(1, N + 1):
    k = A[i - 1]
    tmp = d.copy()
    d = {}
    for a, b, c in dp[i - 1]:
        for j in range(3):
            s = [a, b, c]
            s[j] += k
            s = tuple(sorted(s, reverse=True))
            if s[0] > s[1] + s[2] + S[i - 1]:
                continue

            if s in dp[i]:
                d[s] += tmp[(a, b, c)]
                d[s] %= MOD
            else:
                dp[i].append(s)
                d[s] = tmp[(a, b, c)]

num = 0
for a, b, c in dp[N]:
    if a < b + c:
        num += d[(a, b, c)]
        num %= MOD

print(num)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    s = sum(a) / 2.0
    d = collections.defaultdict(int)
    d[(0,0)] = 1
    e = collections.defaultdict(int)
    for c,i in zip(a[::-1],range(n)):
        for k,v in list(d.items()):
            t = k[0] + c
            kk = (t,k[1]+1)
            k1 = k[1] + 1
            if t >= s:
                kk = (t==s,i+1-k1,n-i-1)
                e[kk] += v
                e[kk] %= mod
            else:
                d[kk] += v
                d[kk] %= mod

    r = 0
    # print('s',s)
    for k,v in e.items():
        if k[0]:
            r += v * pow(2,k[1]) * pow(3,k[2]) * 3
            r -= v * 3
        else:
            r += v * pow(2,k[1]) * pow(3,k[2]) * 3
        r %= mod
        # print('kvr', k,v,r)
    # print(pow(3,n,mod), r)

    return (pow(3,n,mod) - r) % mod


print(main())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(input()) for i in range(N)]
from functools import lru_cache
# @lru_cache(maxsize=None)
# def solve(i, s):
#     if i==-1:
#         if s==0:
#             return 1
#         else:
#             return 0
#     if s<0:
#         return 0
#     return solve(i-1, s) + 2 * solve(i-1, s-A[i])

mod = 998244353
@lru_cache(maxsize=None)
def solve(i, s, m):
    if i==-1:
        if s==0 and m==0:
            return 1
        else:
            return 0
    if s<0 or m<0:
        return 0
    return (solve(i-1, s, m) + solve(i-1, s-A[i], m) + solve(i-1, s, m-A[i])) % mod

ans = 0
su = sum(A)
for sm in range(su//2+1, su*2//3+1):
    l = su - sm
    for s in range(1, sm//2+1):
        m = sm - s
        if not (s <= m <= l):
            continue
        if s==m==l:
            mul = 1
        elif s==m or m==l:
            mul = 3
        else:
            mul = 6
        ans += solve(N-1, s, m) * mul
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    s = sum(a) / 2.0
    d = collections.defaultdict(int)
    d[(0,0)] = 1
    e = collections.defaultdict(int)
    for c,i in zip(a[::-1],range(n)):
        for k,v in list(d.items()):
            t = k[0] + c
            kk = (t,k[1]+1)
            k1 = k[1] + 1
            if t >= s:
                kk = (t,i+1-k1,n-i-1)
                e[kk] += v
                e[kk] %= mod
            else:
                d[kk] += v
                d[kk] %= mod

    r = 0
    # print('s',s)
    for k,v in e.items():
        if k[0] < s:
            continue
        if k[0] == s:
            r += v * pow(2,k[1]) * pow(3,k[2]) * 3
            r -= v * 3
        else:
            r += v * pow(2,k[1]) * pow(3,k[2]) * 3
        r %= mod
        # print('kvr', k,v,r)
    # print(pow(3,n,mod), r)

    return (pow(3,n,mod) - r) % mod


print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
MOD = 998244353
N = int(input())
a = []
for _ in range(N):
    a.append(int(input()))
Lmax = (sum(a)-1)//2

current = defaultdict(int)
current[(0,0,0)] = 1
for i in range(N):
    prev = current
    current = defaultdict(int)
    for k, v in prev.items():
        if k[0]+a[i] <= Lmax:
            current[(k[0]+a[i],k[1],k[2])] += v
            current[(k[0]+a[i],k[1],k[2])] %= MOD
        if k[1]+a[i] <= Lmax:
            current[(k[0],k[1]+a[i],k[2])] += v
            current[(k[0],k[1]+a[i],k[2])] %= MOD
        if k[2]+a[i] <= Lmax:
            current[(k[0],k[1],k[2]+a[i])] += v
            current[(k[0],k[1],k[2]+a[i])] %= MOD

ans = 0
for k, v in current.items():
    ans += v
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

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

d2 = [1]
tmp = 1
for i in range(n):
    tmp = tmp * 2 % MOD
    d2.append(tmp)

s = sum(aaa)
dp = [defaultdict(lambda: 0) for _ in [0] * (s + 1)]
dp[0][0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        for k, p in dp[i].items():
            dp[i + a][k + 1] += p
            dp[i + a][k + 1] %= MOD
    tmp_sum += a

sub = 0
h = (s + 1) // 2
for dd in dp[h:]:
    for k, p in dd.items():
        sub = (sub + d2[n - k] * p * 3) % MOD
if s % 2 == 0:
    dd = dp[h]
    for k, p in dd.items():
        sub = (sub - p * 3) % MOD

ans = (pow(3, n, MOD) - sub) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MOD = 998244353
A = []
for i in range(N):
    A.append(int(input()))
A = sorted(A)
s = sum(A)
dp = [[] for i in range(N + 1)]
dp[0].append((0, 0, 0))
d = {}
d[(0, 0, 0)] = 1
for i in range(1, N + 1):
    k = A[i - 1]
    tmp = d.copy()
    d = {}
    for a, b, c in dp[i - 1]:
        for j in range(3):
            s = [a, b, c]
            s[j] += k
            s = tuple(sorted(s))

            if s in dp[i]:
                d[s] += tmp[(a, b, c)]
                d[s] %= MOD
            else:
                dp[i].append(s)
                d[s] = tmp[(a, b, c)]

num = 0
for a, b, c in dp[N]:
    if a + b > c:
        num += d[(a, b, c)]
        num %= MOD

print(num)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

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

d2 = [1]
tmp = 1
for i in range(n):
    tmp = tmp * 2 % MOD
    d2.append(tmp)

s = sum(aaa)
dp = [defaultdict(lambda: 0) for _ in [0] * (s + 1)]
dp[0][0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        for k, p in dp[i].items():
            dp[i + a][k + 1] += p
            dp[i + a][k + 1] %= MOD
    tmp_sum += a

ans = pow(3, n, MOD)
sub = 0
h = (s + 1) // 2
for dd in dp[h:]:
    for k, p in dd.items():
        sub += d2[n - k] * p * 3
    sub %= MOD
if s % 2 == 0:
    dd = dp[h]
    for k, p in dd.items():
        sub -= p * 3

ans = (ans - sub) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

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

d2 = [1]
tmp = 1
for i in range(n):
    tmp = tmp * 2 % MOD
    d2.append(tmp)

s = sum(aaa)
dp = [defaultdict(lambda: 0) for _ in [0] * (s + 1)]
dp[0][0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dd = dp[i]
        if not dd:
            continue
        for k, p in dd.items():
            dp[i + a][k + 1] += p
    tmp_sum += a

ans = pow(3, n, MOD)
sub = 0
h = (s + 1) // 2
for dd in dp[h:]:
    for k, p in dd.items():
        sub += d2[n - k] * p * 3
    sub %= MOD
if s % 2 == 0:
    dd = dp[h]
    for k, p in dd.items():
        sub -= p * 3

ans = (ans - sub) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict

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

d2 = [1]
tmp = 1
for i in range(n):
    tmp = tmp * 2 % MOD
    d2.append(tmp)

s = sum(aaa)
dp = [defaultdict(lambda: 0) for _ in [0] * (s + 1)]
dp[0][0] = 1
for a in aaa:
    for i in range(s, -1, -1):
        dd = dp[i]
        if not dd:
            continue
        for k, p in dd.items():
            dp[i + a][k + 1] += p

ans = pow(3, n, MOD)
sub = 0
h = (s + 1) // 2
for dd in dp[h:]:
    for k, p in dd.items():
        sub += d2[n - k] * p * 3
    sub %= MOD
if s % 2 == 0:
    dd = dp[h]
    for k, p in dd.items():
        sub -= p * 3

ans = (ans - sub) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    s = sum(a) / 2.0
    d = collections.defaultdict(int)
    d[(0,0)] = 1
    for c in a:
        for k,v in list(d.items()):
            kk = (k[0]+c,k[1]+1)
            d[kk] += v
            d[kk] %= mod

    r = 0
    # print('s',s)
    for k,v in d.items():
        if k[0] < s:
            continue
        if k[0] == s:
            r += v * pow(2,n-k[1]) * 3
            r -= v * 3
        else:
            if n - k[1] > 0:
                r += v * pow(2,n-k[1]) * 3
            else:
                r += v * 3
        r %= mod
    # print(pow(3,n,mod), r, r*3)

    return (pow(3,n,mod) - r) % mod


print(main())

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MOD = 998244353
A = []
for i in range(N):
    A.append(int(input()))
A = sorted(A)
s = sum(A)
dp = [[] for i in range(N + 1)]
dp[0].append((0, 0, 0))
d = {}
d[(0, 0, 0)] = 1
for i in range(1, N + 1):
    k = A[i - 1]
    tmp = d.copy()
    d = {}
    for a, b, c in dp[i - 1]:
        if (a + k, b, c) in dp[i]:
            d[(a + k, b, c)] += tmp[(a, b, c)]
            d[(a + k, b, c)] %= MOD
        else:
            dp[i].append((a + k, b, c))
            d[(a + k, b, c)] = tmp[(a, b, c)]

        if (a, b + k, c) in dp[i]:
            d[(a, b + k, c)] += tmp[(a, b, c)]
            d[(a, b + k, c)] %= MOD
        else:
            dp[i].append((a, b + k, c))
            d[(a, b + k, c)] = tmp[(a, b, c)]

        if (a, b, c + k) in dp[i]:
            d[(a, b, c + k)] += tmp[(a, b, c)]
            d[(a, b, c + k)] %= MOD
        else:
            dp[i].append((a, b, c + k))
            d[(a, b, c + k)] = tmp[(a, b, c)]

num = 0
for a, b, c in dp[N]:
    s = sorted([a, b, c])
    if s[0] + s[1] > s[2]:
        num += d[(a, b, c)]
        num %= MOD

print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
n = int(input())
ai= sorted([int(input()) for i in range(n)])
mod = 998244353

d = defaultdict(int)
d[(0,0,0)] += 1
for a in ai:
    d_tmp = defaultdict(int)
    for (i,j,k), cnt in d.items():
        x,y,z = sorted([i+a, j, k])
        d_tmp[(x,y,z)] += cnt
        if j+a > k:
            d_tmp[(i,k,j+a)] += cnt
        else:
            d_tmp[(i,j+a,k)] += cnt
        d_tmp[(i,j,k+a)] += cnt
    d = d_tmp
ans = 0
for key, value in d.items():
    if key[0]+key[1]>key[2] and key[1]+key[2]>key[0] and key[2]+key[0]>key[1] and key[0]*key[1]*key[2] !=0:
        #print(key, value)
        ans += value
        ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

mod = 998244353
memo = {}
def doit(index, s, c):
    if index >= len(a):
        if s * 2 < suma:
            return 0
        elif s * 2 == suma:
            return ((2 ** (len(a) - c) - 1) * 3) % mod
        else:
            return ((2 ** (len(a) - c)) * 3) % mod
    key = (index, s, c)
    if key not in memo:
        memo[key] = (doit(index + 1, s + a[index], c + 1) + doit(index + 1, s, c)) % mod
    return memo[key]

print((3 ** len(a) - doit(0, 0, 0)) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    s = sum(a) / 2
    d = collections.defaultdict(int)
    d[(0,0)] = 1
    for c in a:
        for k,v in list(d.items()):
            v %= mod
            k1 = k[0]
            k2 = k[1]
            if k1 + c < s:
                if k1 + c <= k2:
                    d[(k1+c,k2)] += v
                else:
                    d[(k2,k1+c)] += v
            if k2 + c < s:
                d[(k1,k2+c)] += v

    r = 0
    for k,v in d.items():
        if sum(k) > s:
            r += v
            r %= mod

    return r


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = sorted([I() for _ in range(n)])
    s = sum(a) / 2
    d = collections.defaultdict(int)
    d[(0,0)] = 1
    for c in a:
        for k,v in list(d.items()):
            v %= mod
            k1 = k[0]
            k2 = k[1]
            if k1 + c < s:
                d[(k1+c,k2)] += v
            if k2 + c < s:
                d[(k1,k2+c)] += v

    r = 0
    for k,v in d.items():
        if sum(k) > s:
            r += v
            r %= mod

    return r


print(main())