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:
n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp = [[[0 for i in range(2)] for i in range(s+1)]for i in range(n+1)]
dp[0][0][0]=0

for i in range(1,n+1):
    for j in range(s+1):
        if j==0:
            b=1
        else:
            b=0
        dp[i][j][0] += (dp[i-1][j][0]+b)
        dp[i][j][0] %= mod
        dp[i][j][1] += (dp[i-1][j][1]+dp[i-1][j][0]+b)
        dp[i][j][1] %= mod
        if j+a[i-1]<=s:
            dp[i][j+a[i-1]][0] += (dp[i-1][j][0]+b)
            dp[i][j][0] %= mod
            dp[i][j+a[i-1]][1] += (b+dp[i-1][j][0])
            dp[i][j][1] %= mod


print(dp[n][s][1])

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp = [[[0 for i in range(2)] for i in range(s+1)]for i in range(n+1)]
dp[0][0][0]=1

for i in range(1,n+1):
    for j in range(s+1):
        if j==0:
            b=1
        else:
            b=0
        dp[i][j][0] += (dp[i-1][j][0]+b)
        dp[i][j][0] %= mod
        dp[i][j][1] += (dp[i-1][j][1]+dp[i-1][j][0]+b)
        dp[i][j][1] %= mod
        if j-a[i-1]>=0:
            dp[i][j][0] += (dp[i-1][j-a[i-1]][0]+b)
            dp[i][j][0] %= mod
            dp[i][j][1] += (b+dp[i-1][j-a[i-1]][0])
            dp[i][j][1] %= mod


print(dp[n][s][1])

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
dp = [[[0 for i in range(3)] for i in range(s+1)]for i in range(n+1)]
dp[0][0][0]=1

for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j][0] %= mod
        dp[i][j][1] += (dp[i-1][j][1]+dp[i-1][j][0])%mod
        dp[i][j][1] %= mod
        dp[i][j][2] += (dp[i-1][j][2]+dp[i-1][j][1]+dp[i-1][j][0])%mod
        dp[i][j][2] %= mod
        if j-a[i-1]>=0:
            dp[i][j][1] += (dp[i-1][j-a[i-1]][1]+dp[i-1][j-a[i-1]][0])%mod
            dp[i][j][1] %= mod
            dp[i][j][2] += (dp[i-1][j-a[i-1]][0]+dp[i-1][j-a[i-1]][1])%mod
            dp[i][j][2] %= mod

#tmp = [[dp[i][j][2]for j in range(s+1)]for i in range(n+1)]
#print(tmp)

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
dp = [[[0 for i in range(3)] for i in range(s+1)]for i in range(n+1)]
dp[0][0][0]=1

for i in range(1,n+1):
    for j in range(s+1):
        dp[i][j][0] += dp[i-1][j][0]
        dp[i][j][0] %= mod
        dp[i][j][1] += dp[i-1][j][1]+dp[i-1][j][0]
        dp[i][j][1] %= mod
        dp[i][j][2] += dp[i-1][j][2]+dp[i-1][j][1]+dp[i-1][j][0]
        dp[i][j][2] %= mod
        if j-a[i-1]>=0:
            dp[i][j][1] += dp[i-1][j-a[i-1]][1]+dp[i-1][j-a[i-1]][0]
            dp[i][j][1] %= mod
            dp[i][j][2] += dp[i-1][j-a[i-1]][0]+dp[i-1][j-a[i-1]][1]
            dp[i][j][2] %= mod

#tmp = [[dp[i][j][2]for j in range(s+1)]for i in range(n+1)]
#print(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline


def convolve(a, b):
    """配列a, bの畳み込みをNTT(number-theoretical transform)によって計算する
    res[k] = (sum{i=0...n}a[i]*b[k-i]) % MOD
    """
    MOD = 998244353
    ROOT = 5

    def ntt(a, inverse=False):
        # バタフライ演算用の配置入れ替え
        for i in range(n):
            j = 0
            for k in range(log_sz):
                j |= (i >> k & 1) << (log_sz - 1 - k)
            if i < j:
                a[i], a[j] = a[j], a[i]

        h = pow(ROOT, (MOD - 1) * pow(n, MOD - 2, MOD) % MOD, MOD)
        if inverse:
            h = pow(h, MOD - 2, MOD)

        # バタフライ演算
        m = 1
        while m < n:
            zeta_pow = 1
            zeta = pow(h, n // (2 * m), MOD)
            for j in range(m):
                for k in range(0, n, 2 * m):
                    s = a[j + k]
                    t = a[j + k + m] * zeta_pow
                    a[j + k] = (s + t) % MOD
                    a[j + k + m] = (s - t) % MOD
                zeta_pow *= zeta
                zeta_pow %= MOD
            m <<= 1

        # 逆変換時には配列のサイズの逆元をかける
        if inverse:
            n_inv = pow(n, MOD - 2, MOD)
            for i in range(n):
                a[i] *= n_inv
                a[i] %= MOD
        return a

    def intt(a):
        return ntt(a, inverse=True)

    n = 1 << (len(a) + len(b) - 1).bit_length()
    log_sz = n.bit_length() - 1
    a += [0] * (n - len(a))
    b += [0] * (n - len(b))

    # in-placeで計算を進めることに注意
    ntt(a), ntt(b)
    for i, val in enumerate(b):
        a[i] *= val
        a[i] %= MOD
    intt(a)

    return a
  

n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353

ptn = [1]
ans = 0
for i in range(n):
    add = [0] * (a[i] + 1)
    add[0] = 1
    add[-1] = 1
    ptn = convolve(ptn, add)[:s + 1]
    if len(ptn)  > s:
        ans += ptn[s]
        ans %= MOD
    ptn[0] += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
import queue
from collections import deque,defaultdict
import heapq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,s = map(int,ipt().split())
    a = [int(i) for i in ipt().split()]
    mod = 998244353
    ans = 0
    for i in range(n):
        dp = np.zeros(s+1,dtype=int)
        dp[0] = 1
        for j in range(i,n):
            aj = a[j]
            dpp = dp*1
            dpp[aj:] += dp[:-aj]
            dpp %= mod
            dp = dpp
            ans = (ans+dp[s]*(n-j))%mod
            dp[s] = 0
    print(ans)
    return

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
dp=[[[0]*3 for i in range(s+1)] for j in range(n+1)]
dp[0][0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      x=dp[i][j-a[i]][0]+dp[i][j-a[i]][1]+dp[i][j][0]+dp[i][j][1]
      dp[i+1][j][1]=x%mod
      dp[i+1][j][2]=(x+dp[i][j][2])%mod
    else:
      dp[i+1][j][0]=dp[i][j][0]%mod
      dp[i+1][j][1]=(dp[i][j][0]+dp[i][j][1])%mod
      dp[i+1][j][2]=(dp[i][j][0]+dp[i][j][1]+dp[i][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
dp=[[[0]*3 for i in range(s+1)] for j in range(n+1)]
dp[0][0][0]=1
for i in range(n):
  for j in range(s+1):
    if j>=a[i]:
      dp[i+1][j][1]=(dp[i][j-a[i]][0]+dp[i][j-a[i]][1]+dp[i][j][0]+dp[i][j][1])%mod
      dp[i+1][j][2]=(dp[i][j-a[i]][0]+dp[i][j-a[i]][1]+dp[i][j][0]+dp[i][j][1]+dp[i][j][2])%mod
    else:
      dp[i+1][j][0]=dp[i][j][0]%mod
      dp[i+1][j][1]=(dp[i][j][1]+dp[i][j][0])%mod
      dp[i+1][j][2]=(dp[i][j][2]+dp[i][j][1]+dp[i][j][0])%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()))
from collections import deque
import itertools
import numpy as np
ls = deque([])

A = np.array(A)
for v in itertools.product([0,1], repeat=N):
    u = np.array(v)
    if S == np.dot(A,u):
        u = list(u)
        i = N
        j = 0
        for k in range(N):
            if u[k] == 1:
                i = min(i,k)
                j = k
        ls.append([i,j])

ans = 0
MOD = 998244353

while ls:
    a = ls.pop()
    ans += (a[0]+1)*(N-a[1]) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
def run():
    N, S = map(int, sysread().split())
    A = [0]+ list(map(int,sysread().split()))
    dp = [[0] * (S+1) for _ in range(N+1)]
    if A[1] <= S:
        dp[1][A[1]] = 1
    mod = 998244353
    for r in range(1, N):
        if A[r+1] <= S:
            dp[r+1][A[r+1]] += r+1
            dp[r + 1][A[r + 1]] %= mod
        for s in range(1,S+1):
            dp[r+1][s] += dp[r][s] + dp[r][s] - dp[r-1][s]
            dp[r+1][s] %= mod
            if s + A[r+1] <= S:
                dp[r+1][s+A[r+1]] += dp[r][s] - dp[r-1][s]
                dp[r + 1][s + A[r + 1]] %= mod
    print(dp[N][S] % mod)






if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n, s = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (s + 1) for _ in range(n + 1)]

mod = 998244353
# dp[i][s] A[i]まで見た時、合計sになる数。
# 各々の地点で新しく開始されるものも有るので毎回dp[i][0]は＋1
dp[0][0] = 1
ans = 0
for i in range(n):
    ni = i + 1
    for j in range(s + 1):
        nj = j
        dp[ni][nj] += dp[i][j]
        dp[ni][nj] %= mod
        nj = j + A[i]
        if nj <= s:
            dp[ni][nj] += dp[i][j]
            dp[ni][nj] %= mod
    dp[ni][0] += 1
    ans += dp[ni][s]
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
ans=0
for l in range(n):
  dp=[[1]+[0]*3000 for _ in range(n+1)]
  for i in range(l,n):
    for j in range(3001):
        dp[i+1][j]=dp[i][j]
        if j-a[i]>=0:
            dp[i+1][j]+=dp[i][j-a[i]]
        dp[i+1][j]%=mod
    #print(dp[i+1][:10])
    ans+=dp[i+1][s]
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,s=map(int,input().split())
a=list(map(int,input().split()))
mod=998244353
ans=0
dp=np.zeros((n+1,3001),np.int64)
for l in range(n):
  dp=np.zeros((n+1,3001),np.int64)
  dp[:,0]=1
  for i in range(l,n):
    dp[i+1]=dp[i]
    dp[i+1,a[i]:]+=dp[i,:-a[i]]
    dp[i+1:]%=mod
    ans+=dp[i+1,s]
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, S = mi()
A = li()

l = [[] for i in range(3005)]
#l[0].append([0, 0])
#print(l)
for i, num in enumerate(A):
    l[num].append([i, i])
    for j in reversed(range(S-num+1)):
        if l[j] != []:
            for st in l[j]:
                if st != [i, i]:
                    l[j+num].append([st[0], i])

ans = 0
for st in l[S]:
    ans = (ans + (st[0]+1)*(N-st[1])) % 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, S = mi()
A = li()

l = [[] for i in range(3005)]
#l[0].append([0, 0])
#print(l)
for i, num in enumerate(A):
    l[num].append([i, i])
    for j in reversed(range(S-num+1)):
        #print(i, j, l)
        if l[j] != []:
            for st in l[j]:
                if st != [i, i]:
                    l[j+num].append([st[0], i])

#print(l[10])
ans = 0
for st in l[S]:
    ans = ans + (st[0]+1)*(N-st[1])
print(ans)

Submission status: Time Limit Exceeded

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

dp = [0] * (S + 1)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
MOD=998244353

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

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

DP[0][0][0]=1
for i,a in enumerate(A,1):
    for s in range(S+1):
        DP[i][s][0]+=DP[i-1][s][0]
        DP[i][s][1]+=DP[i-1][s][0]+DP[i-1][s][1]
        DP[i][s][2]+=DP[i-1][s][0]+DP[i-1][s][1]+DP[i-1][s][2]
        for k in range(3): DP[i][s][k]%=MOD
        if s+a<=S:
            DP[i][s+a][1] += DP[i-1][s][0]+DP[i-1][s][1]
            DP[i][s+a][2] += DP[i-1][s][0]+DP[i-1][s][1]

            DP[i][s+a][1]%=MOD
            DP[i][s+a][2]%=MOD

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    s = [0]*(N+1)
    for i in range(N):
        s[i+1] = s[i] + A[i]
    mod = 998244353
    ans = 0
    # for i in range(N):
    #     for j in range(i+1, N+1):
    #         if s[j] - s[i] == S:
    #             left = i+1
    #             right = N - j + 1
    #             ans += left*right % mod
    #             print(left, right, i, j)
    # print(ans % mod)

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

    for j, a in enumerate(A):
        for i in range(S-1, -1, -1):
            if dp[i][0] > 0 and i+a <= S:
                dp[i+a][0] += dp[i][0]
                if i == 0:
                    dp[i+a][1][((j, j))] = 1
                else:
                    for l, r in dp[i][1]:

                        ll = min(l, j)
                        rr = max(r, j)
                        if (ll, rr) in dp[i+a][1]:
                            dp[i+a][1][(ll, rr)] += dp[i][1][(l, r)]
                        else:
                            dp[i+a][1][(ll, rr)] = dp[i][1][(l, r)] % mod

    for l, r in dp[S][1]:
        ans += (l+1) * (N - r) * dp[S][1][l, r]
        ans %= mod
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,S = MI()
A = LI()
dp = FILL2(0,N+1,S+1)
for i in range(N):
    for j in range(S+1):
        if j>0 and j+A[i]<=S:
            dp[i+1][j+A[i]] += dp[i][j]
        elif j==0 and A[i]<=S:
            dp[i+1][A[i]] += i+1
        dp[i+1][j] += dp[i][j]
#        dp[i+1][j] %= MOD
ans = 0
for i in range(N+1):
    ans += dp[i][S]
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[[0 for i in range(3)] for j in range(3030)] for k in range(3030)]
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][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        dp[i+1][j][0] %= mod
        dp[i+1][j][1] %= mod
        dp[i+1][j][2] %= mod
        if j + A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
            dp[i+1][j+A[i]][2] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
N, S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[[0 for i in range(3)] for j in range(S+1)] for k 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][0] + dp[i][j][1]
        dp[i+1][j][2] += dp[i][j][0] + dp[i][j][1] + dp[i][j][2]
        dp[i+1][j][0] %= mod
        dp[i+1][j][1] %= mod
        dp[i+1][j][2] %= mod
        if j + A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
            dp[i+1][j+A[i]][2] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=998244353
def input(): return sys.stdin.readline().rstrip()

def main():
    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):
        for j in range(S+1):
            dp[i+1][j][0]+=dp[i][j][0]
            dp[i+1][j][0]%=MOD
            dp[i+1][j][1]+=dp[i][j][0]+dp[i][j][1]
            dp[i+1][j][1]%=MOD
            dp[i+1][j][2]+=dp[i][j][0]+dp[i][j][1]+dp[i][j][2]
            dp[i+1][j][2]%=MOD
            if j+A[i]<=S:
                dp[i+1][j+A[i]][1]+=dp[i][j][0]+dp[i][j][1]
                dp[i+1][j+A[i]][1]%=MOD
                dp[i+1][j+A[i]][2]+=dp[i][j][0]+dp[i][j][1]
                dp[i+1][j+A[i]][2]%=MOD
    print(dp[-1][-1][2])

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.buffer.readline

sys.setrecursionlimit(10**6)


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


def slv2(N, S, A):
    from functools import lru_cache, reduce

    M = 998244353

    @lru_cache(maxsize=None)
    def f(i, s):
        if i < 0:
            if s == 0:
                return 1
            else:
                return 0

        if s < 0:
            return 0
        elif s == 0:
            return f(i-1, s) + 1

        return (f(i-1, s-A[i]) + f(i-1, s)) % M

    ans = 0
    for i in range(N-1, -1, -1):
        ans += f(i, S)
        ans %= M
    return ans


def slv(N, S, A):
    M = 998244353
    ans = 0

    dp = [0] * (S+1)
    for a in A:
        dp[0] += 1
        ndp = [0] * (S+1)
        for j in range(S+1):
            ndp[j] += dp[j]
            ndp[j] %= M
            if j+a <= S:
                ndp[j+a] += dp[j]
                ndp[j+a] %= M
        dp = ndp
        ans += dp[S]
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    # print(slv(N, S, A))
    print(slv2(N, S, A))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)



@mt
def slv(N, S, A):
    M = 998244353
    ans = 0

    @lru_cache(maxsize=None)
    def f(i, n):
        if n == 0:
            return N - i + 1
        elif n < 0:
            return 0
        elif i == N:
            return 0 if n != 0 else 1
        return (f(i+1, n-A[i]) + f(i+1, n)) % M

    for i in range(N):
        ans += f(i, S)
        ans %= M

    return ans


def main():
    N, S = read_int_n()
    A = read_int_n()
    print(slv(N, S, A))

    # N = 3000
    # S = random.randint(1, 3000)
    # A = [random.randint(1, 3000) for _ in range(N)]
    # print(slv(N, S, A))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11096062
# 写経

def main():
    MOD = 998244353

    NOT_OPENED = 0
    ONGOING = 1
    CLOSED = 2

    N, S = map(int, input().split())
    *A, = 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):
        for s in range(S + 1):
            dp[i + 1][s][NOT_OPENED] += dp[i][s][NOT_OPENED]
            dp[i + 1][s][ONGOING] += dp[i][s][NOT_OPENED] + dp[i][s][ONGOING]
            dp[i + 1][s][CLOSED] += dp[i][s][NOT_OPENED] + dp[i][s][ONGOING] + dp[i][s][CLOSED]

            ps = s - A[i]
            if ps >= 0:
                dp[i + 1][s][ONGOING] += dp[i][ps][NOT_OPENED] + dp[i][ps][ONGOING]
                dp[i + 1][s][CLOSED] += dp[i][ps][NOT_OPENED] + dp[i][ps][ONGOING]

            dp[i + 1][s][NOT_OPENED] %= MOD
            dp[i + 1][s][ONGOING] %= MOD
            dp[i + 1][s][CLOSED] %= MOD

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections

n,s = map(int,raw_input().split(' '))
ar = map(int, raw_input().split(' '))
def f(a,s): 
	count = 0
	for l in range(len(a)):
		dp = collections.defaultdict(int)
		dp[0] = 1
		for r in range(l, len(a)):
			ndp = collections.defaultdict(int)
			for k in dp: ndp[k+a[r]] += dp[k]
			for k in dp: ndp[k] += dp[k]
			dp = ndp
			count += dp[s]
	
	count %= 998244353
	return count


print f(ar,s)

Submission status: Time Limit Exceeded

Solution code:
import collections

n,s = map(int,raw_input().split(' '))
ar = map(int, raw_input().split(' '))
def f(a,s): 
	count = 0
	for l in range(0, len(a)):
		dp = collections.defaultdict(int)
		dp[0] = 1
		for r in range(l, len(a)):
			ndp = collections.defaultdict(int)
			for k in dp:
				ndp[k+a[r]] += dp[k]
			for k in dp:
				ndp[k] += dp[k]
			dp = ndp
			count += dp[s]
			count %= 998244353
	return count

print f(ar,s)

Submission status: Time Limit Exceeded

Solution code:
import collections

n,s = map(int,raw_input().split(' '))
ar = map(int, raw_input().split(' '))
def f(a,s): 
	count = 0
	for l in range(0, len(a)):
		dp = collections.defaultdict(int)
		dp[0] = 1
		for r in range(l, len(a)):
			for k in range(s)[::-1]:
				dp[k+a[r]] += dp[k]

			count += dp[s]
			count %= 998244353
	return count

print f(ar,s)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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[i][j][k]:Aのindex[i-1]まで見て和がjになっているもの
###kの意味は解説の通り


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][0] %= mod

        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= mod

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

        if j+A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
        
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

mod = 998244353

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

dp = [[[0]*3 for i in range(S+1)] for j in range(N+1)]
###index


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][0] %= mod

        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= mod

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

        if j+A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
        
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] %= mod

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

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 i in range(S+1)] for j 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][0] %= mod

        dp[i+1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i+1][j][1] %= mod

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

        if j+A[i] <= S:
            dp[i+1][j+A[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][1] %= mod
        
            dp[i+1][j+A[i]][2] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+A[i]][2] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
a = tuple(map(int, input().split()))
MOD = 998244353

# dp0 = [[0] * (s + 1) for _ in range(n + 1)]
# dp0[0][0] = 1
# for i in range(n):  # ここをrange(i, n)にすると、f(i, r)の計算ができる
#     for j in range(s + 1):
#         dp0[i + 1][j] += dp0[i][j]  # do NOT use a[i]
#         if j + a[i] <= s:
#             dp0[i + 1][j + a[i]] += dp0[i][j]  # USE a[i]
# # f(1, n) = dp0[n][s]
# # f(1, i) = dp0[i][s] (i = 1, 2, ..., n)
# print('dp0')
# print(*dp0, sep='\n')

dp = [[[0] * 2 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
ans = 0
for i in range(n):
    for j in range(s + 1):
        # i番目の要素は使わない
        dp[i + 1][j][0] += dp[i][j][0]
        dp[i + 1][j][0] %= MOD
        dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i + 1][j][1] %= MOD

        if j + a[i] <= s:
            dp[i + 1][j + a[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i + 1][j + a[i]][1] %= MOD

    ans += dp[i + 1][s][1]
    ans %= MOD
# dp[r][s][1] = \sum_{i=1}^{r} f(i, r)

# print('dp[][][1]')
# for i in range(n + 1):
#     print([dp[i][j][1] for j in range(s + 1)])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
a = tuple(map(int, input().split()))
MOD = 998244353

# dp0 = [[0] * (s + 1) for _ in range(n + 1)]
# dp0[0][0] = 1
# for i in range(n):  # ここをrange(i, n)にすると、f(i, r)の計算ができる
#     for j in range(s + 1):
#         dp0[i + 1][j] += dp0[i][j]  # do NOT use a[i]
#         if j + a[i] <= s:
#             dp0[i + 1][j + a[i]] += dp0[i][j]  # USE a[i]
# # f(1, n) = dp0[n][s]
# # f(1, i) = dp0[i][s] (i = 1, 2, ..., n)
# print('dp0')
# print(*dp0, sep='\n')

dp = [[[0] * 3 for _ in range(s + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(s + 1):
        # i番目の要素は使わない
        dp[i + 1][j][0] += dp[i][j][0]
        dp[i + 1][j][0] %= MOD
        dp[i + 1][j][1] += dp[i][j][0] + dp[i][j][1]
        dp[i + 1][j][1] %= MOD

        if j + a[i] <= s:
            dp[i + 1][j + a[i]][1] += dp[i][j][0] + dp[i][j][1]
            dp[i + 1][j + a[i]][1] %= MOD
# dp[r][s][1] = \sum_{i=1}^{r} f(i, r)

# print('dp[][][1]')
# for i in range(n + 1):
#     print([dp[i][j][1] for j in range(s + 1)])

ans = 0
for i in range(1, n + 1):
    ans += dp[i][s][1]
    ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
data = list(map(int, input().split()))

MOD = 998244353
# dp = [[0]*(3000+1) for _ in range(N)]
# ans = 0

# for i, num in enumerate(data):
#     dp[i][num] = 1
#     for j in range(i):
#         for k in range(S-num, 0, -1):
#             if dp[j][k] >= 1:
#                 dp[j][k+num] += dp[j][k]
#             if k == num:
#                 dp[j][num] += 1
#     for j in range(i+1):
#         ans += dp[j][S]
#     ans %= MOD

# print(ans)

ans = 0
dp = [[] for _ in range(3001)]
dp[0] = [0]
for i, num in enumerate(data):
    for j in range(S-num, -1, -1):
        for item in dp[j]:
            dp[j+num] += [item+(1<<i)]

for item in dp[S]:
    for i in range(N+1):
        if item < (1<<i):
            a = N - i + 1
            break
    for i in range(N):
        if item & (1<<i) != 0:
            b = i + 1
            break
    ans = (a*b+ans)%MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int, input().split())
data = list(map(int, input().split()))

MOD = 998244353
dp = [[0]*(3001) for _ in range(N)]
ans = 0

for i, num in enumerate(data):
    dp[i][num] = 1
    for j in range(i):
        for k in range(3000-num, 0, -1):
            if dp[j][k] >= 1:
                dp[j][k+num] += dp[j][k]
            if k == num:
                dp[j][num] += 1
    for j in range(i+1):
        ans += dp[j][S]
    ans %= MOD

print(ans)