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

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]; one = dp[i][j][1]; two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one
            dp[i+1][j+a][1] %= MOD

answer = dp[N][S][2] % MOD
print(answer)
# 11

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]; one = dp[i][j][1]; two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        dp[i+1][j][1] %= MOD; dp[i+1][j][2] %= MOD
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one
            dp[i+1][j+a][1] %= MOD; dp[i+1][j+a][2] %= MOD
        
answer = dp[N][S][2] % MOD
print(answer)
# 11

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        zero = dp[i][j][0]; one = dp[i][j][1]; two = dp[i][j][2]
        dp[i+1][j][0] += zero
        dp[i+1][j][1] += zero + one
        dp[i+1][j][2] += zero + one + two
        if a + j <= S:
            dp[i+1][j+a][1] = zero + one
            dp[i+1][j+a][2] = zero + one
        dp[i+1][j][2] %= MOD

answer = dp[N][S][2] % MOD
print(answer)
# 11

Submission status: Time Limit Exceeded

Solution code:
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 998244353
N, S = lr()
A = lr()
# dp[i][j][k] i番目まで見て和がjとなる総数
# k=0がL,Rが決まっていない、k=1がLだけ決定、k=2がLとRが決定
dp = [[[0] * 3 for _ in range(S+1)] for _ in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    a = A[i]
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        if a + j <= S: # A[i]を加える時
            dp[i+1][j+a][1] = dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a][2] = dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= MOD
        dp[i+1][j][2] %= MOD

answer = dp[N][S][2] % MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
d = sum(A)
mod = 998244353

"""
多項式係数を使った数え上げでリベンジしてみる。
maspyさんのを参考に実装する。

やってみてわかったけど、実装自体はdpでやったのとほぼ同じ。
多項式係数を使う方法は実質flexibleなdpということ？
"""

f = [0] * (1 + d) # f[i] = (coefficient of degree i)
ans = 0

for i in range(N):
    g = [0] * (1 + d) # g = (1 + f) * (1 + x^{A[i]})
    f[0] += 1
    for j in range(1 + d):
        if j - A[i] < 0:
            g[j] = f[j]
        else:
            g[j] = f[j] + f[j - A[i]]
    ans += g[S]
    ans %= mod
    f = g

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

N, S = map(int, input().split())
A = [0] + list(map(int, input().split()))
mod = 998244353

dp = [0] * (S + 1)
dp2 = [0] * (S + 1)

"""
dp[i][j] = (i個までの数を使ってj点とる組み合わせ)
としたはいいが、f(L, R)をf(1,L)とf(1, R)に分解できずに爆死したのが敗因。

各(L, R)に対してdpするとTLEになるから手詰まりになると思ったわけだけど、
上のdpテーブルを各iに対して使い回しつつ、新たなdpテーブル[1, 0, 0, ...]を
作成して「元のdpテーブルに加算しておけば」dpテーブル一個で1番目スタート、2番目スタート、
..., L番目スタートのdpテーブル全てを考えられる！
（解説放送前半を参考）
"""

# i == 0の時
dp[0] = 1
ans = 0

# i >= 1の時
for i in range(1, N + 1):
    for j in range(S + 1):
        if j - A[i] < 0:
            dp2[j] = dp[j]
        else:
            dp2[j] = dp[j] + dp[j - A[i]]
    ans += dp2[S]
    ans %= mod

    dp = deepcopy(dp2)
    dp[0] += 1
    dp2 = [0] * (S + 1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,S = map(int,input().split())
list = np.int32(input().split())
A = np.zeros((N+1,S+1),dtype=np.int16)
B = np.zeros((N+1,S+1),dtype=np.int16)
C = np.zeros((N+1,S+1),dtype=np.int16)
A[0][0] = 1
for i in range(N):
    for j in range(S+1):
        A[i+1][j]+= A[i][j]
        A[i+1][j]%= 998244353
        B[i+1][j] += A[i][j] + B[i][j]
        B[i+1][j] %= 998244353
        C[i+1][j] += A[i][j]+ B[i][j] + C[i][j]
        C[i+1][j] %= 998244353
        if list[i] + j <= S:
            B[i+1][list[i]+j] += A[i][j] + B[i][j]
            B[i+1][list[i]+j] %= 998244353
            C[i+1][list[i]+j] += A[i][j] + B[i][j]
            C[i+1][list[i]+j] %= 998244353
print(C[N][S] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,S = map(int,input().split())
list = list(map(int,input().split()))
A = np.zeros((N+1,S+1,3),dtype=np.int16)
A[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        A[i+1][j][0] += A[i][j][0]
        A[i+1][j][0] %= 998244353
        A[i+1][j][1] += A[i][j][0] + A[i][j][1]
        A[i+1][j][1] %= 998244353
        A[i+1][j][2] += A[i][j][0] + A[i][j][1] + A[i][j][2]
        A[i+1][j][2] %= 998244353
        if list[i] + j <= S:
            A[i+1][list[i]+j][1] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][1] %= 998244353
            A[i+1][list[i]+j][2] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][2] %= 998244353
print(A[N][S][2] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,S = map(int,input().split())
list = np.int32(input().split())
A = np.zeros((N+1,S+1,3),dtype=np.int16)
A[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        A[i+1][j][0] += A[i][j][0]
        A[i+1][j][0] %= 998244353
        A[i+1][j][1] += A[i][j][0] + A[i][j][1]
        A[i+1][j][1] %= 998244353
        A[i+1][j][2] += A[i][j][0] + A[i][j][1] + A[i][j][2]
        A[i+1][j][2] %= 998244353
        if list[i] + j <= S:
            A[i+1][list[i]+j][1] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][1] %= 998244353
            A[i+1][list[i]+j][2] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][2] %= 998244353
print(A[N][S][2] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,S = map(int,input().split())
list = np.int32(input().split())
A = [[[0,0,0]for i in range(S+1)]for j in range(N+1)]
A[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        A[i+1][j][0] += A[i][j][0]
        A[i+1][j][0] %= 998244353
        A[i+1][j][1] += A[i][j][0] + A[i][j][1]
        A[i+1][j][1] %= 998244353
        A[i+1][j][2] += A[i][j][0] + A[i][j][1] + A[i][j][2]
        A[i+1][j][2] %= 998244353
        if list[i] + j <= S:
            A[i+1][list[i]+j][1] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][1] %= 998244353
            A[i+1][list[i]+j][2] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][2] %= 998244353
print(A[N][S][2] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N,S = map(int,input().split())
list = list(map(int,input().split()))
A = [[[0,0,0]for i in range(S+1)]for j in range(N+1)]
A[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        A[i+1][j][0] += A[i][j][0]
        A[i+1][j][1] += A[i][j][0] + A[i][j][1]
        A[i+1][j][1] %= 998244353
        A[i+1][j][2] += A[i][j][0] + A[i][j][1] + A[i][j][2]
        A[i+1][j][2] %= 998244353
        if list[i] + j <= S:
            A[i+1][list[i]+j][1] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][1] %= 998244353
            A[i+1][list[i]+j][2] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][2] %= 998244353
print(A[N][S][2] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N,S = map(int,input().split())
list = list(map(int,input().split()))
A = [[[0,0,0]for i in range(S+1)]for j in range(N+1)]
A[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        A[i+1][j][0] += A[i][j][0]
        A[i+1][j][0] %= 998244353
        A[i+1][j][1] += A[i][j][0] + A[i][j][1]
        A[i+1][j][1] %= 998244353
        A[i+1][j][2] += A[i][j][0] + A[i][j][1] + A[i][j][2]
        A[i+1][j][2] %= 998244353
        if list[i] + j <= S:
            A[i+1][list[i]+j][1] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][1] %= 998244353
            A[i+1][list[i]+j][2] += A[i][j][0] + A[i][j][1]
            A[i+1][list[i]+j][2] %= 998244353
print(A[N][S][2] % 998244353)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
 
mod = 998244353 
U, S, *A = map(int, read().split())

dp = [[[0]*3 for i in range(3001)] for i in range(3001)]

dp[0][0][0] = 1;
for i in range(U):
    for j in range(S+1):
        dp[i+1][j][0] += dp[i][j][0]%mod
        dp[i+1][j][1] += dp[i+1][j][0] + dp[i][j][1]%mod
        dp[i+1][j][2] += dp[i+1][j][1] + dp[i][j][2]%mod
        if j - A[i] >= 0:
            dp[i+1][j][1] += dp[i][j-A[i]][0]%mod + dp[i][j-A[i]][1]%mod
            dp[i+1][j][2] += dp[i][j-A[i]][0]%mod + dp[i][j-A[i]][1]%mod
    
    
print(dp[U][S][2])

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  read = sys.stdin.buffer.read
  r = 998244353
  U, S, *A = map(int, read().split())
  import copy
  ans = 0
  f = [0]*3010
  for a in A:
      c = copy.deepcopy(f)
      f = [0]*a+c[:-a]
      f = [x+y for x,y in zip(f,c)]
      f[0] += 1
      f[a] += 1
      ans += f[S]
  ans %= r
  print(ans)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read

r = 998244353
 
n, s, *As = map(int, read().split())
import copy
answer = 0
f = [0]*3001
for A in As:
    c = copy.deepcopy(f)
    t = [0]*A
    f = t+c
    f = f[:-A]
    f = [x+y for x,y in zip(f,c)]
    f[0] += 1
    f[A] += 1
    answer += f[s]

answer %= r
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read

MOD = 998244353
 
N, S, *As = map(int, read().split())
import copy
answer = 0
f = [0]*3010
for A in As:
    c = copy.deepcopy(f)
    t = [0]*A
    f = t+c
    f = f[:-A]
    f = [x+y for x,y in zip(f,c)]
    f[0] += 1
    f[A] += 1
    #f %= MOD
    answer += f[S]

answer %= MOD
print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,s = [int(c) for c in input().split()]
a = [int(c) for c in input().split()]
# t[i][j] : 0<=r<...,<l=iについて和がsになるようなf(r,l)の和
# t = [[0]*(s+1) for _ in range(n)]
t = np.zeros((n, s+1), dtype="int64")
if a[0]<=s:
    t[0,a[0]] = 1
for i in range(n):
    t[i,0] = i+2
for i in range(1,n):
    for j in range(1,s+1):
        tt = t[i-1,j]
        if j-a[i]>=0:
            tt += t[i-1,j-a[i]]
        t[i,j] = tt
print(t[:,s].sum()%998244353)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,s = map(int,input().split())
    A = list(map(int,input().split()))
    dp = [[[] for j in range(s+1)] for i in range(n+1)]

    mod = 998244353

    ans = 0

    dp[0][0] = [1]

    for i in range(n):
        for j in range(s):
            if j == 0:
                if A[i] <= s:
                    dp[i+1][A[i]].append(i)
            elif dp[i][j]:
                dp[i+1][j] += dp[i][j]
                if A[i]+j <= s:
                    dp[i+1][j+A[i]] = dp[i][j]
        if dp[i+1][s]:
            for num in dp[i+1][s]:
                ans += ((num+1)*(n-i))%mod
                ans %= mod
            dp[i+1][s] = []

    print(ans%mod)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# fp = open("input/21")
# input = fp.readline
n,s = [int(c) for c in input().split()]
a = [int(c) for c in input().split()]
# t[i][j] : 0<=r<...,<l=iについて和がsになるようなf(r,l)の和
t = [[0]*(s+1) for _ in range(n)]
if a[0]<=s:
    t[0][a[0]] = 1
for i in range(n):
    t[i][0] = i+2
for i in range(1,n):
    for j in range(1,s+1):
        tt = t[i-1][j]
        if j-a[i]>=0:
            tt += t[i-1][j-a[i]]
        t[i][j] = tt
print(sum(t[i][s] for i in range(n))%998244353)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

F = [0 for _ in range(S + 1)]
res = 0

for i in range(N):
    F[0] += 1
    for j in range(S + 1)[::-1]:
        if j - A[i] >= 0:
            F[j] += F[j - A[i]]
    res += F[S]
    res %= MOD

print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = np.zeros(V + 1, dtype=np.int64)
for i, a in enumerate(A):
    dp = np.zeros(V + 1, dtype=np.int64)
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cs[s - a]
    cs = (cs + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int, stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = [0 for _ in range(V + 1)]
for i, a in enumerate(A):
    dp = [0 for _ in range(V + 1)]
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cs[s - a]
    cs = [(a + b) % M for a, b in zip(cs, dp)]
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin

N, S = map(int, stdin.readline().split())
A = list(map(int,stdin.readline().split()))
M = 998244353
V = max(max(A), S)

ans = 0
cs = np.zeros((V + 1,), dtype=np.int32)
for i, a in enumerate(A):
    dp = np.zeros((V + 1,), dtype=np.int32)
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cs[s - a] % M
    cs = (cs + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin

N, S = map(int, stdin.readline().split())
A = np.int32(stdin.readline().split())
M = 998244353

ans = 0
dp = np.zeros((max(S, A.max()) + 1,), dtype=np.int64)
cm = np.zeros_like(dp)
for i, a in enumerate(A):
    dp[:a] = 0
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cm[s - a] % M
    cm = (cm + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353

ans = 0
dp = np.zeros((max(S, A.max()) + 1,), dtype=np.int64)
cm = np.zeros_like(dp)
for i, a in enumerate(A):
    dp[:a] = 0
    dp[a] = i + 1
    for s in range(a + 1, S + 1):
        dp[s] = cm[s - a] % M
    cm = (cm + dp) % M
    ans = (ans + (N - i) * dp[S]) % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, S = map(int, input().split())
A = np.int32(input().split())
M = 998244353

dp = np.zeros((N, max(S, A.max()) + 1), dtype=np.int64)
for i, a in enumerate(A):
    dp[i, a] = i + 1
    for s in range(a + 1, S + 1):
        dp[i, s] = dp[:i, s - a].sum() % M

ans = 0
for i in range(N):
    ans += (N - i) * dp[i, S]
    ans = ans % M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353


class DP:

    def __init__(self, X, Y, Z):
        self._X = X
        self._Y = Y
        self._Z = Z
        self._list = [0] * (X * Y * Z)
    
    def get(self, x, y, z):
        return self._list[x*(self._Y*self._Z) + y*self._Z + z]
    
    def set(self, x, y, z, v):
        self._list[x*(self._Y*self._Z) + y*self._Z + z] = v


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

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

    # dp[0][0][0] = 1
    dp.set(0, 0, 0, 1)

    for i in range(0, N):
        for s in range(0, S+1):
            # dp[i+1][s][0] = dp[i][s][0]
            dp.set(i+1, s, 0, dp.get(i, s, 0))
            if s - A[i] >= 0:
                # dp[i+1][s][1] = (dp[i][s][1] + dp[i][s][0] + dp[i][s-A[i]][1] + dp[i][s-A[i]][0]) % MOD
                dp.set(i+1, s, 1, (dp.get(i, s, 1) + dp.get(i, s, 0) + dp.get(i, s-A[i], 1) + dp.get(i, s-A[i], 0)) % MOD)
                # dp[i+1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0] + dp[i][s-A[i]][1] + dp[i][s-A[i]][0]) % MOD
                dp.set(i+1, s, 2, (dp.get(i, s, 2) + dp.get(i, s, 1) + dp.get(i, s, 0) + dp.get(i, s-A[i], 1) + dp.get(i, s-A[i], 0)) % MOD)
            else:
                # dp[i+1][s][1] = (dp[i][s][1] + dp[i][s][0]) % MOD
                dp.set(i+1, s, 1, (dp.get(i, s, 1) + dp.get(i, s, 0)) % MOD)
                # dp[i+1][s][2] = (dp[i][s][2] + dp[i][s][1] + dp[i][s][0]) % MOD
                dp.set(i+1, s, 2, (dp.get(i, s, 2) + dp.get(i, s, 1) + dp.get(i, s, 0)) % MOD)

    # print(dp[N][S][2])
    print(dp.get(N, S, 2))


solve()

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353


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

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

    dp[0][0][0] = 1

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

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


solve()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp[i+1][j][0] += dp[i][j][0]
        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp[i+1][j+a][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+a][2] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][0] %= MOD
        dp[i+1][j][1] %= MOD
        dp[i+1][j][2] %= MOD
ans = dp[N][S][2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
mod = 998244353

N, S = map(int, input().split())
A = [int(x) for x in input().split()]
dp = [[[0]*3 for j in range(S+1)] for i in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    dpi = dp[i]
    for j in range(S+1):
        dpij = dpi[j]
        if A[i] <= j:
            dpija = dpi[j-A[i]]
            dp[i+1][j][0] = dpij[0]
            dp[i+1][j][1] = (dpij[1]+dpija[1]+dpija[0]*(i+1)%mod)%mod
            dp[i+1][j][2] = (dpij[2]+dpija[0]*(i+1)*(N-i)%mod+dpija[1]*(N-i)%mod)%mod
        else:
            dp[i+1][j][0] = dpij[0]
            dp[i+1][j][1] = dpij[1]
            dp[i+1][j][2] = dpij[2]
print(dp[N][S][2])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
mod = 998244353

N, S = map(int, input().split())
A = [int(x) for x in input().split()]
dp = [[[0]*3 for j in range(S+max(A)+1)] for i in range(N+1)]
dp[0][0][0] = 1
cnt = 0
for i in range(N):
    for j in range(S+1):
        dp[i+1][j][0] = dp[i][j][0]
        dp[i+1][j][1] = dp[i][j][1]
        dp[i+1][j][2] = dp[i][j][2]
        if A[i] <= j:
            dp[i+1][j][1] += dp[i][j-A[i]][0]*(i+1)
            dp[i+1][j][1] %= mod
            dp[i+1][j][1] += dp[i][j-A[i]][1]
            dp[i+1][j][2] %= mod
            dp[i+1][j][2] += dp[i][j-A[i]][1]*(N-i)
            dp[i+1][j][2] %= mod
    if A[i] == S:
        cnt = (cnt+(i+1)*(N-i))%mod
print((dp[N][S][2]+cnt)%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
mod = 998244353

N, S = map(int, input().split())
A = [int(x) for x in input().split()]
dp = [[[0]*3 for j in range(S+max(A)+1)] for i in range(N+1)]
dp[0][0][0] = 1
for i in range(N):
    for j in range(S+1):
        dp[i+1][j][0] = dp[i][j][0]
        dp[i+1][j][1] = dp[i][j][1]
        dp[i+1][j][2] = dp[i][j][2]
        if A[i] <= j:
            dp[i+1][j][1] += dp[i][j-A[i]][0]*(i+1)
            dp[i+1][j][1] %= mod
            dp[i+1][j][1] += dp[i][j-A[i]][1]
            dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j-A[i]][0]*(i+1)*(N-i)
            dp[i+1][j][2] %= mod
            dp[i+1][j][2] += dp[i][j-A[i]][1]*(N-i)
            dp[i+1][j][2] %= mod
print(dp[N][S][2])

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 998244353

ans = 0
dp = [0] * (S + 1)

for a in A:
    dp[0] += 1
    for s in range(S + 1)[:: -1]:
        if s + a <= S:
            dp[s + a] += dp[s]
    ans += dp[S]

print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        for k in range(3):
            if dp[i][j][k] == 0:
                continue
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
ans = dp[N][S][2] % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

def main():
    import sys

    def input(): return sys.stdin.readline().strip()
    def list2d(a, b, c): return [[c] * b for i in range(a)]
    def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
    def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
    def ceil(x, y=1): return int(-(-x // y))
    def INT(): return int(input())
    def MAP(): return map(int, input().split())
    def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
    def Yes(): print('Yes')
    def No(): print('No')
    def YES(): print('YES')
    def NO(): print('NO')
    sys.setrecursionlimit(10 ** 9)
    INF = 10 ** 18
    MOD = 998244353

    N, S = MAP()
    A = LIST()

    # dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
    dp = list3d(N+1, S+1, 3, 0)
    dp[0][0][0] = 1
    for i, a in enumerate(A):
        for j in range(S+1):
            for k in range(3):
                if dp[i][j][k] == 0:
                    continue
                for l in range(k, 3):
                    # aを総和に足さない遷移は全部OK
                    dp[i+1][j][l] += dp[i][j][k]
                    dp[i+1][j][l] %= MOD
                    # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                    if j+a <= S and k != 2 and l != 0:
                        dp[i+1][j+a][l] += dp[i][j][k]
                        dp[i+1][j+a][l] %= MOD
    ans = dp[N][S][2]
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

acc = list(accumulate(A))
# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # 枝刈り
        if j > acc[i]:
            break
        for k in range(3):
            if dp[i][j][k] == 0:
                continue
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                dp[i+1][j][l] %= MOD
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
                    dp[i+1][j+a][l] %= MOD
ans = dp[N][S][2]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        for k in range(3):
            if dp[i][j][k] == 0:
                continue
            dp[i][j][k] %= MOD
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
ans = dp[N][S][2] % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        for k in range(3):
            if dp[i][j][k] == 0:
                continue
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                dp[i+1][j][l] %= MOD
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
                    dp[i+1][j+a][l] %= MOD
ans = dp[N][S][2]
print(ans)