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:
#!/usr/bin/env python3
import sys
import copy
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 998244353  # type: int


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, S: int, A: "List[int]"):
    dp = array(S+1, 3, initial=0)
    dp[0][0] = 1
    for i in range(N):
        dp_past = copy.deepcopy(dp)
        # t=0軸
        for s in range(S+1):
            # A[i]を使う
            if s-A[i] >= 0:
                dp[s][0] += dp_past[s-A[i]][0]
                dp[s][0] %= MOD

        # t=1軸
        for s in range(S+1):
            if s-A[i] >= 0:
                dp[s][1] += dp_past[s-A[i]][1]
                dp[s][1] %= MOD
        if A[i] <= S:
            dp[A[i]][1] += i+1
            dp[s][1] %= MOD

        # t=2軸
        for s in range(S+1):
            if s-A[i] >= 0:
                dp[s][2] += (dp[s][1]-dp_past[s][1]) * (N-i)
                dp[s][2] %= MOD

    print(dp[S][2])

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 998244353  # type: int


def array(*args, initial=0):
    pre = "["*len(args)
    post = ""
    for a in args[::-1]:
        post += " for _ in range("+str(a)+")]"
    S = pre + str(initial) + post
    return eval(S)


def solve(N: int, S: int, A: "List[int]"):
    dp = array(N+1, S+1, 3, initial=0)
    dp[0][0][0] = 1
    for i in range(N):
        # t=0軸
        for s in range(S+1):
            # A[i]を使わない
            dp[i+1][s][0] = dp[i][s][0]
            # A[i]を使う
            if s-A[i] >= 0:
                dp[i+1][s][0] += dp[i][s-A[i]][0]
                dp[i+1][s][0] %= MOD

        # t=1軸
        for s in range(S+1):
            dp[i+1][s][1] = dp[i][s][1]
            if s-A[i] >= 0:
                dp[i+1][s][1] += dp[i][s-A[i]][1]
                dp[i+1][s][1] %= MOD
        if A[i] <= S:
            dp[i+1][A[i]][1] += i+1
            dp[i+1][s][1] %= MOD

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

    # print(*dp, sep="\n")
    print(dp[N][S][2])
    # print("")
    # p = [[dp[i][s][2] for s in range(S+1)] for i in range(N+1)]
    # print(*p, sep="\n")

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, S, A)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

# i indicade low , c indicade column
for i,w in enumerate(a):
    for c in range(s+1):
        dp[i][c]+=dp[i-1][c]
    for c in range(s-w+1):
        dp[i][c+w]+=dp[i-1][c]
    ans+=dp[i][-1]
    ans%=998244353

print(ans)

Submission status: Time Limit Exceeded

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

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

# i indicade low , c indicade column
for i,w in enumerate(a):
    for c in range(s+1):
        dp[c][i]+=dp[c][i-1]
    for c in range(s-w+1):
        dp[c+w][i]+=dp[c][i-1]
    ans+=dp[-1][i]
    ans%=998244353

print(ans)

Submission status: Time Limit Exceeded

Solution code:
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*6003
for a in a:
 for j in range(s,0,-1):d[a+j]+=d[j]
 d[a]-=~i;c+=d[s];i+=1
print(c%(998244353))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
mod = 998244353
N, S = list(map(int, input().split()))
A = list(map(int, input().split()))

ans = 0
num = [0] * 6020
for i in range(N):
    for j in range(3010, 0, -1):
        num[A[i]+j] += num[j]
        num[A[i]+j] %= mod
    num[A[i]] += i+1
    num[A[i]] %= mod
    ans += num[S] * (N - i)
    ans %= mod
    num[S] = 0
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[i][j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]

# 初期条件
dp[0][0][0] = 1

# 配るDP
for i, a in enumerate(A):
    for j in range(S + 1):
        for k in range(3):

            for n in range(k, 3): # 配る先の状態
                dp[i + 1][j][n] = (dp[i + 1][j][n] + dp[i][j][k]) % MOD
                if (n != 0 and k != 2) and j + a <= S:
                    dp[i + 1][j + a][n] = (dp[i + 1][j + a][n] + dp[i][j][k]) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
import sys
input = sys.stdin.readline

N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[i][j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)]

def main():
    # 初期条件
    dp[0][0][0] = 1

    # 配るDP
    for i, a in enumerate(A):
        for j in range(S + 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][1]) % MOD
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][j][2]) % MOD

            if j + a <= S:
                # 左端を決定
                dp[i + 1][j + a][1] = (dp[i + 1][j + a][1] + dp[i][j][0] * (i + 1) % MOD) % MOD
                # 両端を決定
                dp[i + 1][j + a][2] = (dp[i + 1][j + a][2] + dp[i][j][0] * (i + 1) % MOD * (N - i) % MOD) % MOD
                # 選択する
                dp[i + 1][j + a][1] = (dp[i + 1][j + a][1] + dp[i][j][1]) % MOD
                # 右端を決定
                dp[i + 1][j + a][2] = (dp[i + 1][j + a][2] + dp[i][j][1] * (N - i) % MOD) % MOD

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
import sys
input = sys.stdin.readline

N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[i][j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[0] * 3 for _ in range(S + 2)]
nxt = [[0] * 3 for _ in range(S + 2)]

def main():
    # 初期条件
    dp[0][0] = 1

    # 配るDP
    for i, a in enumerate(A):
        for j in range(S + 1):
            # 選択しない
            nxt[j][0] = (nxt[j][0] + dp[j][0]) % MOD
            # 左端を決定
            nxt[min(S + 1, j + a)][1] = (nxt[min(S + 1, j + a)][1] + dp[j][0] * (i + 1) % MOD) % MOD
            # 両端を決定
            nxt[min(S + 1, j + a)][2] = (nxt[min(S + 1, j + a)][2] + dp[j][0] * (i + 1) % MOD * (N - i) % MOD) % MOD

            # 選択しない
            nxt[j][1] = (nxt[j][1] + dp[j][1]) % MOD
            # 選択する
            nxt[min(S + 1, j + a)][1] = (nxt[min(S + 1, j + a)][1] + dp[j][1]) % MOD
            # 右端を決定
            nxt[min(S + 1, j + a)][2] = (nxt[min(S + 1, j + a)][2] + dp[j][1] * (N - i) % MOD) % MOD

            # 選択しない
            nxt[j][2] = (nxt[j][2] + dp[j][2]) % MOD

        for j in range(S + 1):
            for k in range(3):
                dp[j][k], nxt[j][k] = nxt[j][k], 0

    print(dp[S][2])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
import sys
input = sys.stdin.readline

N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[i][j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[0] * 3 for _ in range(S + 2)]

def main():
    # 初期条件
    dp[0][0] = 1

    # 配るDP
    for i, a in enumerate(A):
        nxt = [[0] * 3 for _ in range(S + 2)]
        for j in range(S + 1):
            # 選択しない
            nxt[j][0] = (nxt[j][0] + dp[j][0]) % MOD
            # 左端を決定
            nxt[min(S + 1, j + a)][1] = (nxt[min(S + 1, j + a)][1] + dp[j][0] * (i + 1) % MOD) % MOD
            # 両端を決定
            nxt[min(S + 1, j + a)][2] = (nxt[min(S + 1, j + a)][2] + dp[j][0] * (i + 1) % MOD * (N - i) % MOD) % MOD

            # 選択しない
            nxt[j][1] = (nxt[j][1] + dp[j][1]) % MOD
            # 選択する
            nxt[min(S + 1, j + a)][1] = (nxt[min(S + 1, j + a)][1] + dp[j][1]) % MOD
            # 右端を決定
            nxt[min(S + 1, j + a)][2] = (nxt[min(S + 1, j + a)][2] + dp[j][1] * (N - i) % MOD) % MOD

            # 選択しない
            nxt[j][2] = (nxt[j][2] + dp[j][2]) % MOD

        for j in range(S + 1):
            for k in range(3):
                dp[j][k] = nxt[j][k]

    print(dp[S][2])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
import sys
input = sys.stdin.readline

N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[0] * 3 for _ in range(6000)]

def main():
    # 初期条件
    dp[0][0] = 1

    # 配るDP
    for i, a in enumerate(A):
        nxt = [[0] * 3 for _ in range(6000)]
        for j in range(S + 1):
            # 選択しない
            nxt[j][0] = (nxt[j][0] + dp[j][0]) % MOD
            # 左端を決定
            nxt[j + a][1] = (nxt[j + a][1] + dp[j][0] * (i + 1) % MOD) % MOD
            # 両端を決定
            nxt[j + a][2] = (nxt[j + a][2] + dp[j][0] * (i + 1) % MOD * (N - i) % MOD) % MOD

            # 選択しない
            nxt[j][1] = (nxt[j][1] + dp[j][1]) % MOD
            # 選択する
            nxt[j + a][1] = (nxt[j + a][1] + dp[j][1]) % MOD
            # 右端を決定
            nxt[j + a][2] = (nxt[j + a][2] + dp[j][1] * (N - i) % MOD) % MOD

            # 選択しない
            nxt[j][2] = (nxt[j][2] + dp[j][2]) % MOD

        for j in range(S + 1):
            for k in range(3):
                dp[j][k] = nxt[j][k]

    print(dp[S][2])

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[0] * 3 for _ in range(6000)]
nxt = [[0] * 3 for _ in range(6000)]

# 初期条件
dp[0][0] = 1

# 配るDP
for i, a in enumerate(A):
    for j in range(S + 1):
        # 選択しない
        nxt[j][0] = (nxt[j][0] + dp[j][0]) % MOD
        # 左端を決定
        nxt[j + a][1] = (nxt[j + a][1] + dp[j][0] * (i + 1) % MOD) % MOD
        # 両端を決定
        nxt[j + a][2] = (nxt[j + a][2] + dp[j][0] * (i + 1) * (N - i) % MOD) % MOD

        # 選択しない
        nxt[j][1] = (nxt[j][1] + dp[j][1]) % MOD
        # 選択する
        nxt[j + a][1] = (nxt[j + a][1] + dp[j][1]) % MOD
        # 右端を決定
        nxt[j + a][2] = (nxt[j + a][2] + dp[j][1] * (N - i) % MOD) % MOD

        # 選択しない
        nxt[j][2] = (nxt[j][2] + dp[j][2]) % MOD

    for j in range(S + 1):
        for k in range(3):
            dp[j][k] = nxt[j][k]
    nxt = [[0] * 3 for _ in range(6000)]

print(dp[S][2])

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
def main():
    N,S = map(int, input().split())
    A = [int(i) for i in input().split()]

    MOD = 998244353

    # dp[i][j][k]
    # i: i番目
    # j: 区間の総和
    # k: 区間の選択状態
    # 0: 区間未選択
    # 1: 左端のみ選択済み
    # 2: 両端が選択済み
    dp = [[[0] * 3 for _ in range(6100)] for _ in range(N + 1)]

    # 初期条件
    dp[0][0][0] = 1

    # 配るDP
    for i, a in enumerate(A):
        for j in range(S + 1):
            # 選択しない
            dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD
            # 左端を決定
            dp[i + 1][j + a][1] = (dp[i + 1][j + a][1] + dp[i][j][0] * (i + 1) % MOD) % MOD
            # 両端を決定
            dp[i + 1][j + a][2] = (dp[i + 1][j + a][2] + dp[i][j][0] * (i + 1) % MOD * (N - i) % MOD) % MOD

            # 選択しない
            dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % MOD
            # 選択する
            dp[i + 1][j + a][1] = (dp[i + 1][j + a][1] + dp[i][j][1]) % MOD
            # 右端を決定
            dp[i + 1][j + a][2] = (dp[i + 1][j + a][2] + dp[i][j][1] * (N - i) % MOD) % MOD

            # 選択しない
            dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][j][2]) % MOD

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[i][j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[[0] * 3 for _ in range(6000)] for _ in range(N + 1)]

# 初期条件
dp[0][0][0] = 1

# 配るDP
for i, a in enumerate(A):
    for j in range(S + 1):
        # 選択しない
        dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % MOD
        # 左端を決定
        dp[i + 1][j + a][1] = (dp[i + 1][j + a][1] + dp[i][j][0] * (i + 1) % MOD) % MOD
        # 両端を決定
        dp[i + 1][j + a][2] = (dp[i + 1][j + a][2] + dp[i][j][0] * (i + 1) * (N - i) % MOD) % MOD

        # 選択しない
        dp[i + 1][j][1] = (dp[i + 1][j][1] + dp[i][j][1]) % MOD
        # 選択する
        dp[i + 1][j + a][1] = (dp[i + 1][j + a][1] + dp[i][j][1]) % MOD
        # 右端を決定
        dp[i + 1][j + a][2] = (dp[i + 1][j + a][2] + dp[i][j][1] * (N - i) % MOD) % MOD

        # 選択しない
        dp[i + 1][j][2] = (dp[i + 1][j][2] + dp[i][j][2]) % MOD

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

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[i][j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[[0] * 3 for _ in range(6000)] for _ in range(N + 1)]

f = lambda i, j, k, n: (dp[i][j][k] + n) % MOD

# 初期条件
dp[0][0][0] = 1

# 配るDP
for i, a in enumerate(A):
    for j in range(S + 1):
        # 選択しない
        dp[i + 1][j][0] = f(i + 1, j, 0, dp[i][j][0])
        # 左端を決定
        dp[i + 1][j + a][1] = f(i + 1, j + a, 1, dp[i][j][0] * (i + 1))
        # 両端を決定
        dp[i + 1][j + a][2] = f(i + 1, j + a, 2, dp[i][j][0] * (i + 1) * (N - i) % MOD)

        # 選択しない
        dp[i + 1][j][1] = f(i + 1, j, 1, dp[i][j][1])
        # 選択する
        dp[i + 1][j + a][1] = f(i + 1, j + a, 1, dp[i][j][1])
        # 右端を決定
        dp[i + 1][j + a][2] = f(i + 1, j + a, 2, dp[i][j][1] * (N - i) % MOD)

        # 選択しない
        dp[i + 1][j][2] = f(i + 1, j, 2, dp[i][j][2])

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

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
N,S = map(int, input().split())
A = [int(i) for i in input().split()]

MOD = 998244353

# dp[i][j][k]
# i: i番目
# j: 区間の総和
# k: 区間の選択状態
# 0: 区間未選択
# 1: 左端のみ選択済み
# 2: 両端が選択済み
dp = [[[0] * 3 for _ in range(6000)] for _ in range(N + 1)]

f = lambda i, j, k, n: (dp[i][j][k] + n) % MOD

# 初期条件
dp[0][0][0] = 1

# 配るDP
for i, a in enumerate(A):
    for j in range(S + 1):
        # 選択しない
        dp[i + 1][j][0] = f(i + 1, j, 0, dp[i][j][0])
        # 左端を決定
        dp[i + 1][j + a][1] = f(i + 1, j + a, 1, dp[i][j][0] * (i + 1))
        # 両端を決定
        dp[i + 1][j + a][2] = f(i + 1, j + a, 2, dp[i][j][0] * (i + 1) * (N - i))

        # 選択しない
        dp[i + 1][j][1] = f(i + 1, j, 1, dp[i][j][1])
        # 選択する
        dp[i + 1][j + a][1] = f(i + 1, j + a, 1, dp[i][j][1])
        # 右端を決定
        dp[i + 1][j + a][2] = f(i + 1, j + a, 2, dp[i][j][1] * (N - i))

        # 選択しない
        dp[i + 1][j][2] = f(i + 1, j, 2, dp[i][j][2])

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

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

    for a in A:
        for s in range(S, -1, -1):
            d1 = dp[s][0]
            d2 = (dp[s][1] + (0 if s - a < 0 else dp[s - a][1]) + d1) % mod
            d3 = (dp[s][2] + (0 if s - a < 0 else dp[s - a][1]) + d2) % mod
            dp[s] = (d1, d2, d3)

    print((dp[S][2] - dp[S][1]) % mod)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

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

    for a in A:
        for s in range(S, -1, -1):
            dp[s] = (
                dp[s][0],
                (
                    (dp[s][1] + dp[s][0]) % mod
                    + (0 if s - a < 0 else dp[s - a][0] + dp[s - a][1]) % mod
                )
                % mod,
                (
                    sum(dp[s]) % mod
                    + (0 if s - a < 0 else dp[s - a][1] + dp[s - a][0]) % mod
                )
                % mod,
            )

    print(dp[S][2])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import queue

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

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

    for a in A:
        for s in range(S, -1, -1):
            dp[s] = [
                dp[s][0] % mod,
                (
                    (dp[s][1] + dp[s][0]) % mod
                    + (0 if s - a < 0 else dp[s - a][0] + dp[s - a][1]) % mod
                )
                % mod,
                (
                    sum(dp[s]) % mod
                    + (0 if s - a < 0 else dp[s - a][1] + dp[s - a][0]) % mod
                )
                % mod,
            ]

    print(dp[S][2])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import queue

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

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

    for i, a in enumerate(A):
        for s in range(S + 1):
            dp[i + 1][s][0] += dp[i][s][0]
            dp[i + 1][s][1] += (dp[i][s][1] + dp[i][s][0]) % mod + (
                0 if s - a < 0 else dp[i][s - a][0] + dp[i][s - a][1]
            ) % mod
            dp[i + 1][s][2] += (
                sum(dp[i][s]) % mod
                + (0 if s - a < 0 else dp[i][s - a][1] + dp[i][s - a][0]) % mod
            )

            dp[i + 1][s][0] %= mod
            dp[i + 1][s][1] %= mod
            dp[i + 1][s][2] %= mod

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import queue

input = sys.stdin.readline
sys.setrecursionlimit(100000)
# mod = 10 ** 9 + 7
mod = 998244353


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


def read_index():
    return map(lambda x: int(x) - 1, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v

    def __str__(self):
        return str(self.v)

    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n)


def main():
    N, S = read_values()
    A = read_list()

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

    for i, a in enumerate(A):
        for s in range(S + 1):
            dp[i + 1][s][0] += dp[i][s][0]
            dp[i + 1][s][1] += (
                dp[i][s][1]
                + dp[i][s][0]
                + (0 if s - a < 0 else dp[i][s - a][0] + dp[i][s - a][1])
            )
            dp[i + 1][s][2] += (
                dp[i][s][2]
                + dp[i][s][1]
                + dp[i][s][0]
                + (0 if s - a < 0 else dp[i][s - a][1] + dp[i][s - a][0])
            )

            dp[i + 1][s][0] %= mod
            dp[i + 1][s][1] %= mod
            dp[i + 1][s][2] %= mod

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[[]] * n for i in range(n)]
mod = 998244353
ans = 0
for d in range(n):
  for i in range(n-d):
    if d == 0:
      dp[i][i+d].append(a[i])
    elif d == 1:
      dp[i][i+d] = dp[i][i] + dp[i+1][i+1]
      dp[i][i+d].append(a[i]+a[i+1])
    else:
      dp[i][i+d] = dp[i][i+d-1] + dp[i+1][i+d]
      dp[i][i+d].append(a[i]+a[i+d])
      for j in range(len(dp[i+1][i+d-1])):
        dp[i][i+d].remove(dp[i+1][i+d-1][j])
        dp[i][i+d].append(a[i]+a[i+d]+dp[i+1][i+d-1][j])
    ans += dp[i][i+d].count(s)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:

MOD = 998244353


def main():
    global A, MOD
    N,S = map(int, input().split())
    A = list(map(int, input().split()))
    dp = [[[0 for k in range(3)] for i in range(S+1)] for j in range(N)]


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

    print(dp[N-1][S][2]%MOD)

main()

Submission status: Time Limit Exceeded

Solution code:
# DP tabelを3つに分けた

import numpy as np

def main():
    MOD = 998244353

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

    DP0 = np.array([[0] * (S + 1) for _ in range(N + 1)], dtype = np.int64)
    DP1 = np.array([[0] * (S + 1) for _ in range(N + 1)], dtype = np.int64)
    DP2 = np.array([[0] * (S + 1) for _ in range(N + 1)], dtype = np.int64)

    DP0[0, 0] = 1

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

        DP2[i + 1, S] = (DP1[i, S] + DP2[i, S])
        if a <= S:
            DP2[i + 1, S] += DP0[i, S - a] + DP1[i, S - a]
        DP2[i + 1, S] %= MOD

    print (DP2[N, S])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# numpyで書換えた
import numpy as np

def main():
    MOD = 998244353

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

    DP = np.array([[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)], dtype = np.int64)
    DP[0, 0, 0] = 1

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

    DP0 = [[0] * (S + 1) for _ in range(N + 1)]
    DP1 = [[0] * (S + 1) for _ in range(N + 1)]
    DP2 = [[0] * (S + 1) for _ in range(N + 1)]

    DP0[0][0] = 1

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

        DP2[i + 1][S] = (DP1[i][S] + DP2[i][S])
        if a <= S:
            DP2[i + 1][S] += DP0[i][S - a] + DP1[i][S - a]
        DP2[i + 1][S] %= MOD

    print (DP2[N][S])

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import numpy as np
    MOD = 998244353

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

    DP = np.array([[[0] * 3 for _ in range(S + 1)] for _ in range(N + 1)], dtype = np.int64)
    DP[0, 0, 0] = 1

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