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:
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)
l.sort()
ll=[[0 for i in range(n+1)] for i in range(sl+1)]
ll[0][0]=1
nmax=1
imax=0
for a in l:
    for i in range(imax,-1,-1):
        for j in range(nmax):
            ll[i+a][j+1]+=ll[i][j]
    nmax+=1
    imax+=a
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:
import sys
def input():
    return sys.stdin.readline()[:-1]

N = int(input())
A = [int(input()) for i in range(N)]
A.sort()
cumA = [0]
for a in A:
    cumA.append(a+cumA[-1])
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
    if s>cumA[i+1] or m>cumA[i+1]:
        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:
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
nmax=1
imax=0
for a in l:
    for i in range(imax,-1,-1):
        for j in range(nmax):
            ll[i+a][j+1]+=ll[i][j]
    nmax+=1
    imax+=a
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:
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 = {}
    dp[i - 1] = sorted(dp[i - 1])
    flag = False
    for a, b, c in dp[i - 1]:
        if flag:
            break
        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]:
                flag = True
                break

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

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

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

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

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

sum_now += a

for i in range(1, N):
	a = aaa[i]
	sum_now += a
	for j in range(sum_now + 1):

		if (j >= a):
			DP[i][j] = DP[i-1][j]*2 + DP[i-1][j-a]
		else:
			DP[i][j] = DP[i-1][j]*2

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

		if (j >= a):
			DP2[i][j] = DP2[i-1][j] + DP2[i-1][j-a]
		else:
			DP2[i][j] = DP2[i-1][j]

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


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

Submission status: Time Limit Exceeded

Solution code:
LEN = 1000

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

dp = [[[0 for i in range(LEN)] for j in range(LEN)] for k in range(LEN)]
dp[0][0][0] = 1

s = 0
for a in A:
    for i in range(s+1):
        for j in range(s+1-i):
            k = s - i - j
            dp[i+a][j][k] += dp[i][j][k]
            dp[i][j+a][k] += dp[i][j][k]
            dp[i][j][k+a] += dp[i][j][k]
    s += a

res = 0
for i in range(1, LEN):
    for j in range(1, LEN):
        k = s - i - j
        if k>0 and i+j>k and j+k>i and k+i>j:
            res += dp[i][j][k]
print(res%998244353)

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)])
    if n > 300 or max(a) > 300:
        return 1 / 0
    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,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],mod) * pow(3,k[1],mod) * 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:
N = int(input())

rgb = [[0,0,0] for i in range(3)]

a = int(input())
rgb[0][0] += a
rgb[1][1] += a
rgb[2][2] += a

for n in range(1,N):
    a = int(input())
    #print('len',len(rgb))
    RGB = []
    for i in range(len(rgb)):
        li1,li2,li3 = [0,0,0],[0,0,0],[0,0,0]

        for j in range(3):
            li1[j] += rgb[i][j]
            li2[j] += rgb[i][j]
            li3[j] += rgb[i][j]
        
        li1[0] += a
        RGB.append(li1)

        li2[1] += a
        RGB.append(li2)
        
        li3[2] += a
        RGB.append(li3)
    rgb = RGB
    #print(rgb)

#print(rgb)

ans = 0
for i in range(len(rgb)):
    li = rgb[i]
    #print(li)
    if max(li) < sum(li) - max(li):
        ans += 1
        ans %= 998244353

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]:
                break

            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

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 = [[0] * (n + 1) for _ in [0] * (s + 1)]
dp[0][0] = 1
tmp_sum = 0
for a in aaa:
    for i in range(tmp_sum, -1, -1):
        dpi = dp[i]
        dpa = dp[i + a]
        for k in range(n):
            if dpi[k] > 0:
                dpa[k + 1] = (dpa[k + 1] + dpi[k]) % MOD
    tmp_sum += a

sub = 0
h = (s + 1) // 2
for dpi in dp[h:]:
    for k in range(n + 1):
        if dpi[k] > 0:
            sub = (sub + d2[n - k] * dpi[k] * 3) % MOD
if s % 2 == 0:
    dpi = dp[h]
    for k in range(n + 1):
        if dpi[k] > 0:
            sub = (sub - dpi[k] * 3) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
n = int(input())
nums = []
for _ in range(n):
  nums.append(int(input()))

total = sum(nums)
nums = sorted(nums, reverse=True)

def sort_3(ar):
  a, b, c = ar
  if a >= b and b >= c:
    return (a,b,c)
  if a >= c and c >= b:
    return (a,c,b)
  if b >= a and a >= c:
    return (b,a,c)
  if b >= c and c >= a:
    return (b,c,a)
  if c >= a and a >= b:
    return (c,a,b)
  if c >= b and b >= a:
    return (c,b,a)

counts_old = {(nums[0], 0, 0): 1}
for i in range(1, n):
  #print('round {}'.format(i))
  v = nums[i]
  counts = {}
  for (a,b,c) in counts_old:
    for t in [[a+v, b, c], [a, b+v, c], [a, b, c+v]]:
      #aa, bb, cc = sorted(t, reverse=True)
      aa, bb, cc = sort_3(t)
      if aa > total / 2:
        continue
      if (aa, bb, cc) not in counts:
        counts[(aa, bb, cc)] = 0
      counts[(aa, bb, cc)] = (counts[(aa, bb, cc)] + counts_old[(a,b,c)]) % mod
  counts_old = counts
  #print(len(counts))

cnt = 0
for (a, b, c) in counts:
  if a + b > c and b + c > a and c + a > b:
    cnt += counts[(a, b, c)]
    cnt = cnt % mod
print((cnt * 3) % mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=2**25)
def search(d, r, g, b):
    if d == N:
        return r>0<g and b>0 and abs(r-g) < b < r+g
    else:
        return (search(d+1, r+a[d], g, b) + search(d+1, r, g+a[d], b) + search(d+1, r, g, b+a[d])) % 998244353

print(search(0,0,0,0))

Submission status: Time Limit Exceeded

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

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

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

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

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

sum_now += a

for i in range(1, N):
	a = aaa[i]
	for j in range(sum_now + 1):
		DP[i][j] += DP[i-1][j] * 2
		while (DP[i][j] > mod):
			DP[i][j] -= mod
		DP[i][j + a] += DP[i-1][j]


		DP2[i][j] += DP2[i-1][j]
		while (DP[i][j] > mod):
			DP[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:
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(A[i]):
    dp[i][j] = (dp[i-1][j]*2) %mod
  for j in range(A[i], temp_sum+1):
    dp[i][j] = (dp[i-1][j]*2 + dp[i-1][j-A[i]]) %mod
  for j in range(temp_sum+1, temp_sum+1 + A[i]):
    dp[i][j] = (dp[i-1][j-A[i]]) %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:
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,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],mod) * pow(3,k[1],mod) * 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 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],mod) * pow(3,k[1],mod) * 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:
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(a[i], min(s, sup) + 1):
            g = s - r
            dp[i + 1][r][g] += dp[i][r - a[i]][g]
            dp[i + 1][r][g] %= MOD
        for g in range(a[i], min(s, sup) + 1):
            r = s - g
            dp[i + 1][r][g] += dp[i][r][g - a[i]]
            dp[i + 1][r][g] %= MOD
        for r in range(min(s, sup) + 1):
            g = s - r
            dp[i + 1][r][g] += dp[i][r][g]
            dp[i + 1][r][g] %= MOD
            # Bに対応

ans = sum(dp[N][r][g] for r in range(sup + 1) for g in range(sup + 1) if total - r - g <= sup)
ans %= MOD
print(ans)