Problem:


Score : 600 points

Problem Statement

Given are a sequence of N integers A_1, A_2, \ldots, A_N and a positive integer S.

For a pair of integers (L, R) such that 1\leq L \leq R \leq N, let us define f(L, R) as follows:

f(L, R) is the number of sequences of integers (x_1, x_2, \ldots , x_k) such that L \leq x_1 < x_2 < \cdots < x_k \leq R and A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(L, R) over all pairs of integers (L, R) such that 1\leq L \leq R\leq N. Since this sum can be enormous, print it modulo 998244353.

Constraints

All values in input are integers.

1 \leq N \leq 3000

1 \leq S \leq 3000

1 \leq A_i \leq 3000

Input

Input is given from Standard Input in the following format:

N S
A_1 A_2 ... A_N

Output

Print the sum of f(L, R), modulo 998244353.

Sample Input 1

3 4
2 2 4

Sample Output 1

5

The value of f(L, R) for each pair is as follows, for a total of 5.

f(1,1) = 0

f(1,2) = 1 (for the sequence (1, 2))

f(1,3) = 2 (for (1, 2) and (3))

f(2,2) = 0

f(2,3) = 1 (for (3))

f(3,3) = 1 (for (3))

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

152



Sample input:
3 4
2 2 4


Sample output:
5

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

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

    for i in range(N):
        DP[i + 1][0][0] = DP[i][0][0] 
        DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD

        DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2])
        if a <= S:
            DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
        DP[i + 1][S][2] %= MOD

    print (DP[N][S][2])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = tuple(map(int, input().split()))

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

    for i in range(N):
        DP[i + 1][0][0] = DP[i][0][0] 
        DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD

        DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2]) % MOD
        if a <= S:
            DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
        DP[i + 1][S][2] %= MOD

    print (DP[N][S][2])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 998244353

    N, S = map(int, input().split())
    A = list(map(int, input().split()))

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

    for i in range(N):
        DP[i + 1][0][0] = DP[i][0][0] 
        DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
        a = A[i]
        if a > S:
            for j in range(1, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
        else:
            for j in range(1, a):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
            for j in range(a, S + 1):
                DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD

        DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2]) % MOD
        if a <= S:
            DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
        DP[i + 1][S][2] %= MOD

    print (DP[N][S][2])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

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

for i in range(N):
    DP[i + 1][0][0] = DP[i][0][0] 
    DP[i + 1][0][1] = DP[i][0][0] + DP[i][0][1]
    a = A[i]
    if a > S:
        for j in range(1, S + 1):
            DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
    else:
        for j in range(1, a):
            DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1]) % MOD #以前から合計jになっている場合のみOK
        for j in range(a, S + 1):
            DP[i + 1][j][1] = (DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]) % MOD

    DP[i + 1][S][2] = (DP[i][S][1] + DP[i][S][2]) % MOD
    if a <= S:
        DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
    DP[i + 1][S][2] %= MOD

print (DP[N][S][2])

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

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

N, S = map(int, input().split())
A = list(map(int, input().split()))

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

for i in range(N):
    DP[i + 1][0][0] = DP[i][0][0] 
    a = A[i]
    for j in range(S + 1):
        if j == 0: #左側を決めて合計0になるのは、
            # DP[i + 1][j][0] = DP[i][j][0] 
            DP[i + 1][j][1] = DP[i][j][0] + DP[i][j][1]
        elif j < a: #左側を決めて合計jになるとき、ただしaはjより大きいので使えない
            # DP[i + 1][j][0] = DP[i][j][0] 
            DP[i + 1][j][1] = DP[i][j][0] + DP[i][j][1] #以前から合計jになっている場合のみOK
        else: #左側を決めて合計j > aになるとき, aだけでは足りない = 左側はこれより前で決まっている
            DP[i + 1][j][1] = DP[i][j][0] + DP[i][j][1] + DP[i][j - a][0] + DP[i][j - a][1]
        # DP[i + 1][j][0] %= MOD
        DP[i + 1][j][0] %= MOD
    DP[i + 1][S][2] = DP[i][S][1] + DP[i][S][2]
    if a <= S:
        DP[i + 1][S][2] += DP[i][S - a][0] + DP[i][S - a][1]
    DP[i + 1][S][2] %= MOD

print (DP[N][S][2])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


############ ---- Input Functions ---- ############
def in_int():
    return (int(input()))


def in_list():
    return (list(map(int, input().split())))


def in_str():
    s = input()
    return (list(s[:len(s) - 1]))


def in_ints():
    return (map(int, input().split()))


n ,  k = in_ints()


a = [0] + in_list()

ans = 0

m = {}
mod = 998244353

def fun(i, val):
    if (i, val) not in m:
        if i < 0 or val < 0:
            m[(i, val)] = 0
        elif val == 0:
            m[(i, val)] = i+1
        else:
            m[(i, val)] = fun(i-1, val - a[i]) + fun(i - 1, val)

    return m[(i, val)]


i = 0
j = 0
for xx in a[1:]:
    i+=1
    l = fun(i-1, k- xx)

    ans  += ((l%mod)*((n-i+1)%mod))%mod
    ans%=mod


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)


############ ---- Input Functions ---- ############
def in_int():
    return (int(input()))


def in_list():
    return (list(map(int, input().split())))


def in_str():
    s = input()
    return (list(s[:len(s) - 1]))


def in_ints():
    return (map(int, input().split()))


n ,  k = in_ints()


a = [0] + in_list()

ans = 0

m = {}


def fun(i, val):
    if (i, val) not in m:
        if i < 0 or val < 0:
            m[(i, val)] = []
        elif val == 0:
            m[(i, val)] = [i]
        else:
            m[(i, val)] = fun(i-1, val - a[i]) + fun(i - 1, val)

    return m[(i, val)]


i = 0
j = 0
for xx in a[1:]:
    i+=1
    l = fun(i-1, k- xx)
    for j in l:
        ans  += (j+1)*(n-i+1)


print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, s = list(map(int, readline().split()))
    a = list(map(int, readline().split()))

    dp = [[0] * 6005 for _ in range(2)]
    dp[0][0] = 1
    dp[1][0] = 2
    dp[1][a[0]] = 1

    for ai in range(1, n):
        dp_temp = [0] * 6005
        w = a[ai]
        dp_temp[0] = 1
        for si in range(s + 1):
            dp_temp[si] += dp[ai][si]
            dp_temp[si + w] += dp[ai][si]
        dp.append(dp_temp)

    ans = 0
    for ai in range(n + 1):
        ans += dp[ai][s]

    print(ans % 998244353)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, s = list(map(int, readline().split()))
    a = list(map(int, readline().split()))

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

    for ai in range(n):
        w = a[ai]
        dp[ai][0] += 1

        for si in range(s + 1):
            dp[ai + 1][si] += dp[ai][si]
            dp[ai + 1][si + w] += dp[ai][si]

    ans = 0
    for ai in range(n+1):
        ans += dp[ai][s]

    print(ans % 998244353)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, s = list(map(int, readline().split()))
    a = list(map(int, readline().split()))

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

    for ai in range(n):
        a_cur = a[ai]
        dp[ai][0] += 1
        if a_cur <= s:
            dp[ai][a_cur] += 1
        for si in range(s + 1):
            dp[ai][si] += dp[ai - 1][si]
            if (si - a_cur) >= 0:
                dp[ai][si] += dp[ai - 1][si - a_cur]

    ans = 0
    for ai in range(n):
        ans += dp[ai][s]

    print(ans%998244353)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,s = list(map(int,input().split())); arr = list(map(int,input().split()))

mod = 998244353
ans = 0
dp = [0]*(s+1)

for i in range(n):
    dp[0] += 1
    tmp = arr[i]
    for j in range(s,tmp-1,-1):
        dp[j] += dp[j-tmp]
        dp[j] %= mod
    ans += dp[s]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,s = list(map(int,input().split())); arr = list(map(int,input().split()))

mod = 998244353
ans = 0
dp = [list() for i in range(s+1)]
if arr[0] < s+1:
    dp[arr[0]].append([0])

for i in range(1,n):
    tmp = arr[i]
    for j in range(s-tmp,0,-1):
        if dp[j]:
            dp[j+tmp] += [info+[i] for info in dp[j]]
    if tmp < s+1:
        dp[tmp].append([i])

for cmb in dp[s]:
    ans += (cmb[0]+1) * (n-cmb[-1])
    ans %= mod
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from fractions import gcd

NN = 202020
# MOD = 10**9+7
MOD = 998244353
INF = float("inf")

n, k = map(int, input().split())
A = list(map(int, input().split()))
dp = [[[0]*3 for _ in range(k+1)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(k+1):
        dp[i+1][j][0] = (dp[i+1][j][0] + dp[i][j][0])%MOD
        dp[i+1][j][1] = (dp[i+1][j][1] + dp[i][j][0] + dp[i][j][1])%MOD
        dp[i+1][j][2] = (dp[i+1][j][2] + dp[i][j][0] + dp[i][j][1] + dp[i][j][2])%MOD
        if j + A[i] <= k:
            dp[i+1][j+A[i]][1] = (dp[i+1][j+A[i]][1] + dp[i][j][0] + dp[i][j][1])%MOD
            dp[i+1][j+A[i]][2] = (dp[i+1][j+A[i]][2] + dp[i][j][0] + dp[i][j][1])%MOD

print(dp[n][k][2])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import copy

r = 998244353

(n, s) = map(int, input().split())

a = list(map(int, input().split()))

# s => comb
itbl = {}
rtbl = {}

for i in range(n):
    ai = a[i]
    
    nitbl = copy.copy(itbl)

    if ai in nitbl:
        nitbl[ai] = (nitbl[ai] + i + 1) % r
    else:
        nitbl[ai] = i + 1

    if ai in rtbl:
        rtbl[ai] += (i + 1) * (n - i)
    else:
        rtbl[ai] = (i + 1) * (n - i)

        
    for sk in itbl:
        if sk + ai in nitbl:
            nitbl[sk + ai] = (nitbl[sk + ai] + itbl[sk]) % r
        else:
            nitbl[sk + ai] = itbl[sk]

        if sk + ai in rtbl:
            rtbl[sk + ai] = (rtbl[sk + ai] + itbl[sk] * (n - i)) % r
        else:
            rtbl[sk + ai] = (itbl[sk] * (n - i)) % r
            
    itbl = nitbl
    
print(rtbl.get(s, 0))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import copy

r = 998244353

(n, s) = map(int, input().split())

a = list(map(int, input().split()))

# s => comb
itbl = {}
rtbl = {}

for i in range(n):
    ai = a[i]
    
    #itbl
    nitbl = copy.copy(itbl)
    if ai in nitbl:
        nitbl[ai] = (nitbl[ai] + i + 1) % r
    else:
        nitbl[ai] = i + 1

    for sk in itbl:
        if sk + ai in nitbl:
            nitbl[sk + ai] = (nitbl[sk + ai] + itbl[sk]) % r
        else:
            nitbl[sk + ai] = itbl[sk]

    #rtbl
    if ai in rtbl:
        rtbl[ai] += (i + 1) * (n - i)
    else:
        rtbl[ai] = (i + 1) * (n - i)

    for sk in itbl:
        if sk + ai in rtbl:
            rtbl[sk + ai] = (rtbl[sk + ai] + itbl[sk] * (n - i)) % r
        else:
            rtbl[sk + ai] = (itbl[sk] * (n - i)) % r
            
    itbl = nitbl
    
print(rtbl.get(s, 0))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python3
import copy

(n, s) = map(int, input().split())

a = list(map(int, input().split()))

# s => comb
itbl = {}
rtbl = {}

for i in range(n):
    ai = a[i]
    
    #itbl
    nitbl = copy.copy(itbl)
    if ai in nitbl:
        nitbl[ai] += i + 1
    else:
        nitbl[ai] = i + 1

    for sk in itbl:
        if sk + ai in nitbl:
            nitbl[sk + ai] += itbl[sk]
        else:
            nitbl[sk + ai] = itbl[sk]

    #rtbl
    if ai in rtbl:
        rtbl[ai] += (i + 1) * (n - i)
    else:
        rtbl[ai] = (i + 1) * (n - i)

    for sk in itbl:
        if sk + ai in rtbl:
            rtbl[sk + ai] += itbl[sk] * (n - i)
        else:
            rtbl[sk + ai] = itbl[sk] * (n - i)
            
    itbl = nitbl
    
print(rtbl.get(s, 0))

Submission status: Time Limit Exceeded

Solution code:
MOD=998244353
N, S=map(int, input().split())
A=list(map(int, input().split()))
tmp=max(A+[S])
dp=[[[0]*3 for s in range(tmp+1)] for i in range(N)]
dp[0][0][0]=1
dp[0][A[0]][1]=1
dp[0][A[0]][2]=1

for i in range(1, N):
    dp[i][0][0]=i+1
    dp[i][A[i]][1]=1
    dp[i][A[i]][2]=1
    for s in range(A[i]):
        dp[i][s][1]=dp[i-1][s][1]
        dp[i][s][2]=(dp[i-1][s][2]+dp[i-1][s][1])%MOD
        
    for s in range(A[i], S+1):
        dp[i][s][1]=(dp[i][s-A[i]][0]+dp[i-1][s-A[i]][1]+dp[i-1][s][1])%MOD
        dp[i][s][2]=(dp[i-1][s][2]+dp[i][s-A[i]][0]+dp[i-1][s][1]+dp[i-1][s-A[i]][1])%MOD
        
print(dp[-1][S][2])

Submission status: Time Limit Exceeded

Solution code:
MOD=998244353
N, S=map(int, input().split())
A=list(map(int, input().split()))
tmp=max(A+[S])

dp=[[[0]*3 for s in range(tmp+1)] for i in range(N)]
dp[0][0][0]=1
dp[0][A[0]][1]=1
dp[0][A[0]][2]=1

for i in range(1, N):
    dp[i][0][0]=i+1
    dp[i][A[i]][1]=1
    dp[i][A[i]][2]=1
    for s in range(A[i]):
        dp[i][s][1]=dp[i-1][s][1]
        dp[i][s][2]=(dp[i-1][s][2]+dp[i-1][s][1])%MOD
        
    for s in range(A[i], S+1):
        dp[i][s][1]=(dp[i][s-A[i]][0]+dp[i-1][s-A[i]][1]+dp[i-1][s][1])%MOD
        dp[i][s][2]=(dp[i-1][s][2]+dp[i][s-A[i]][0]+dp[i-1][s][1]+dp[i-1][s-A[i]][1])%MOD
        
print(dp[-1][S][2])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
mod = 998244353
N, S = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

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

for k in range(0, N):
  for s in range(1, S+1):
    dp[k+1][s] += (2 * dp[k][s] - dp[k-1][s]) % mod
    if (s + A[k+1]) <= S:
      dp[k+1][s+A[k+1]] += (dp[k][s] - dp[k-1][s]) % mod

  if A[k+1] <= S:
    dp[k+1][A[k+1]] += k+1

print(dp[N][S] % mod)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
mod = 998244353
N, S = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

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

for k in range(0, N):
  for s in range(1, S+1):
    dp[k+1][s] += (2 * dp[k][s] - dp[k-1][s]) % mod
  if S > A[k+1]:
    for s in range(1,S-A[k+1]+1):
      dp[k+1][s+A[k+1]] += (dp[k][s] - dp[k-1][s]) % mod
  if A[k+1] <= S:
    dp[k+1][A[k+1]] += k+1

print(dp[N][S] % mod)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
mod = 998244353
N, S = list(map(int, input().split()))
A = [0] + list(map(int, input().split()))

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

for k in range(0, N):
  for s in range(0, S+1):
    dp[k+1][s] += (2 * dp[k][s] - dp[k-1][s]) % mod
  if S > A[k+1]:
    for s in range(1,S-A[k+1]+1):
      dp[k+1][s+A[k+1]] += (dp[k][s] - dp[k-1][s]) % mod
  if A[k+1] <= S:
    dp[k+1][A[k+1]] += k+1

print(dp[N][S] % mod)

Submission status: Time Limit Exceeded

Solution code:
# not solved
# CPython: TLE
# PyPy: TLE
from copy import deepcopy

MOD_VAL = 998244353


def main():
    _, target = [int(v) for v in input().split(' ')]
    nums = [int(v) for v in input().split(' ')]
    dp = [0 for _ in range(target + 1)]
    dp[0] = 1
    ans = 0
    for n in nums:
        tmp_dp = deepcopy(dp)
        for k, v in enumerate(tmp_dp[:-1]):
            if n + k <= target:
                dp[n + k] += v
        dp[0] += 1
        ans = (ans + dp[target]) % MOD_VAL
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# not solved
# CPython: TLE
# PyPy: TLE

MOD_VAL = 998244353


def add_value(dp, n_k, k, v, target):
    # if k + n <= target:
    if n_k <= target:
        # if k + n in dp.keys():
        if n_k in dp.keys():
            # dp[k + n] += v
            dp[n_k] += v
        else:
            # dp[k + n] = v
            dp[n_k] = v


def main():
    _, target = [int(v) for v in input().split(' ')]
    nums = [int(v) for v in input().split(' ')]
    dp = {0: 0, target: 0}
    ans = 0
    for n in nums:
        dp[0] += 1
        iters = list(dp.items())
        for k, v in iters:
            n_k = k + n
            if n_k <= target:
                add_value(dp, n_k, k, v, target)
        ans = (ans + dp[target]) % MOD_VAL
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# not solved
# CPython: TLE
# PyPy: TLE

MOD_VAL = 998244353


def add_value(dp, n, k, v, target):
    if k + n <= target:
        if k + n in dp.keys():
            dp[k + n] += v
        else:
            dp[k + n] = v


def main():
    _, target = [int(v) for v in input().split(' ')]
    nums = [int(v) for v in input().split(' ')]
    dp = {0: 0, target: 0}
    ans = 0
    for n in nums:
        dp[0] += 1
        # tmp_dp = dp.copy()
        iters = list(dp.items())
        # for k, v in dp.items():
        for k, v in iters:
            if k + n <= target:
                # add_value(tmp_dp, n, k, v, target)
                add_value(dp, n, k, v, target)
        # dp = tmp_dp
        ans = (ans + dp[target]) % MOD_VAL
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# not solved

MOD_VAL = 998244353


def add_value(dp, n, k, v, target):
    if k + n <= target:
        if k + n in dp.keys():
            dp[k + n] += v
        else:
            dp[k + n] = v


def main():
    _, target = [int(v) for v in input().split(' ')]
    nums = [int(v) for v in input().split(' ')]
    dp = {0: 0, target: 0}
    ans = 0
    for n in nums:
        dp[0] += 1
        tmp_dp = dp.copy()
        for k, v in dp.items():
            if k + n <= target:
                add_value(tmp_dp, n, k, v, target)
        dp = tmp_dp
        ans = (ans + dp[target]) % MOD_VAL
    print(int(ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))

    dp0 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp1 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp2 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp0[0][0] = Mint(1)
    for i in range(N):
        a = A[i]
        dp0i = dp0[i]
        dp1i = dp1[i]
        dp2i = dp2[i]
        dp0n = dp0[i+1]
        dp1n = dp1[i+1]
        dp2n = dp2[i+1]
        for j in range(S+1):
            dp0ij = dp0i[j]
            dp1ij = dp1i[j]

            dp0n[j] += dp0ij
            dp1n[j] += dp1ij
            dp2n[j] += dp2i[j]

            if j+a > S: continue
            to1 = dp0ij * Mint(i+1)
            to1 += dp1ij
            dp1n[j+a] += to1
            to1 *= Mint(N-i)
            dp2n[j+a] += to1

    print(dp2[N][S])

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += other.value
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= other.value
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(other.value)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * other.value % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(other.value)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))

    dp0 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp1 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp2 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp0[0][0] += 1
    for i in range(N):
        a = A[i]
        dp0i = dp0[i]
        dp1i = dp1[i]
        dp2i = dp2[i]
        dp0n = dp0[i+1]
        dp1n = dp1[i+1]
        dp2n = dp2[i+1]
        for j in range(S+1):
            dp0ij = dp0i[j]
            dp1ij = dp1i[j]

            dp0n[j] += dp0ij
            dp1n[j] += dp1ij
            dp2n[j] += dp2i[j]

            if j+a > S: continue
            to1 = dp0ij * (i+1)
            to1 += dp1ij
            dp1n[j+a] += to1
            to1 *= (N-i)
            dp2n[j+a] += to1

    print(dp2[N][S])

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,S = map(int, input().split())
    A = list(map(int, input().split()))

    dp0 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp1 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp2 = [[Mint() for _ in range(S+1)] for _ in range(N+1)]
    dp0[0][0] += 1
    for i in range(N):
        a = A[i]
        dp0i = dp0[i]
        dp1i = dp1[i]
        dp2i = dp2[i]
        dp0n = dp0[i+1]
        dp1n = dp1[i+1]
        dp2n = dp2[i+1]
        for j in range(S+1):
            dp0ij = dp0i[j]
            dp1ij = dp1i[j]

            dp0n[j] += dp0ij
            dp1n[j] += dp1ij
            dp2n[j] += dp2i[j]

            if j+a > S: continue
            to1 = dp0ij * (i+1) + dp1ij
            dp1n[j+a] += to1
            dp2n[j+a] += to1 * (N-i)

    print(dp2[N][S])

MOD = 998244353
class Mint:
    def __init__(self, value=0):
        self.value = value % MOD
        if self.value < 0: self.value += MOD

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, MOD
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        if u < 0: u += MOD
        return u

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value += Mint.get_value(other)
        if self.value >= MOD: self.value -= MOD
        return self
    def __add__(self, other):
        new_obj = Mint(self.value)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value -= Mint.get_value(other)
        if self.value < 0: self.value += MOD
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % MOD
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other)
        self *= other.inverse()
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other))
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    main()