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: Accepted

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

    dp = [[0]*3001 for _ in [0]*n]
    dp[0][a[0]] = 1
    for j, i in enumerate(a[1:]):
        dp[j+1][i] += (j+2)
        for k in range(3001-i):
            dp[j+1][i+k] = (dp[j+1][i+k]+dp[j][k]) % mod
        for k in range(3001):
            dp[j+1][k] = (dp[j+1][k]+dp[j][k]) % mod
    print(sum([dp[i][s] for i in range(n)]) % mod)


main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, s = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353

ans = 0
B = [0] * (s+1)
for i in range(n):
    for j in range(s, -1, -1):
        if j-A[i] >= 0:
            B[j] = (B[j] + B[j-A[i]])%mod
    if A[i] < len(B):
        B[A[i]] += i+1
    ans = (ans + B[s])%mod#*(n-i)
    # B[s] = 0
    # print(B)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, S = map(int, input().split())
a = list(map(int, input().split()))
mod = 998244353

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i in range(N):
  dp[i][0] = i + 1
  for j in range(S + 1):
    if j + a[i] < S:
      dp[i + 1][j + a[i]] += dp[i][j]
      dp[i + 1][j + a[i]] %= mod
    elif j + a[i] == S:
      dp[i + 1][j + a[i]] += dp[i][j] * (N - i)
      dp[i + 1][j + a[i]] %= mod
    dp[i + 1][j] += dp[i][j]
    dp[i + 1][j] %= mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
n, s = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 998244353

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

dp[0][0] = 1

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

ans = 0

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

print(ans)

Submission status: Accepted

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

#左端で考える
#左からiまででjを作る場合の数

dp=[0]*S
dp[0]=1
ans=0

for i in range(N):
    h=dp[:]
    a=A[i]
    if a>S:
        continue
    if a==S:
        ans=(ans+(i+1)*(N-i))%mod
        continue
        
    h[a]=(h[a]+i+1)%mod
    for j in range(a+1,S):
        h[j]=(h[j]+dp[j-a])%mod
    ans=(ans+dp[S-a]*(N-i))%mod
    dp=h
    
print(ans)

Submission status: Accepted

Solution code:
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
X = [0] * 3001
pre = 0
ans = 0
P = 998244353
for i, a in enumerate(A):
    for j in range(S, a, -1):
        X[j] = (X[j] + X[j-a]) % P
    X[a] = (X[a] + i + 1) % P
    ans = (ans + (X[S] - pre) * (N - i)) % P
    pre = X[S]
print(ans)

Submission status: Accepted

Solution code:
from numpy import *
M=998244353
N,S,*A=map(int,open(0).read().split())
a=0
f=zeros(S+1,int)
for b in A:
  f[0]+=1
  f[b:] += f[:-b].copy()
  f%=M
  a+=f[S]
print(a%M)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read


n,s,*a = [int(i) for i in read().split()]
MOD = 998244353
 

def mul(c,m,dp): #multiply (1-x^c) up to x^m
    for i in range(m,c-1,-1):
        dp[i] += dp[i-c]
        dp[i] %= MOD
 
dp = [0]*(s+1)

ans = 0
for c in a:
    dp[0] += 1
    mul(c,s,dp)
    ans += dp[s]
    #print(dp)    

print(ans%MOD)

Submission status: Accepted

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

dp = [0] * (3000 + 1)
dp[0] = 1
ans = 0
for i in range(n):
    for w in range(3000 + 1)[::-1]:
        # 選ぶとき
        if w - a[i] > 0:
            dp[w] += dp[w - a[i]]
        if w - a[i] == 0:
            dp[w] += dp[w - a[i]] * (i + 1)
        dp[w] %= MOD
    ans += dp[s]
    ans %= MOD
print(ans % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

MOD = 998244353

N, S, *As = map(int, read().split())

U = 3010
answer = 0
f = np.zeros(U, np.int64)
for A in As:
    f[0] += 1
    f[A:] += f[:-A].copy()
    f %= MOD
    answer += f[S]

answer %= MOD
print(answer)

Submission status: Accepted

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

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

for i in range(1,N):
    for j in range(0,S+1):
        if j>A[i]:
            dp[i][j]=(dp[i-1][j]+dp[i-1][j-A[i]])%mod
        elif j==A[i]:
            dp[i][j]=(dp[i-1][j]+(i+1))%mod
        else:
            dp[i][j]=dp[i-1][j]

ans=0
for i in range(0,N):
    ans=(ans+dp[i][S])%mod

print(ans)

Submission status: Accepted

Solution code:
n, s = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
mod = 998244353

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

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

ans = 0
for i in range(1, n + 1):
    ans += dp[i][-1] * 1#(n + 1 - i)
    ans %= mod
print(ans)

Submission status: Accepted

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

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

if a[0]<=s: dp[0][a[0]]=1

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

ans=0
for i in range(n):
    ans+=dp[i][s]
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input=sys.stdin.readline
    n,s=map(int,input().split())
    A=list(map(int,input().split()))
    mod=998244353
    dp=[[0]*(s+1) for _ in range(n+1)]
    dp[0][0]=1
    for i in range(1,n+1):
        for j in range(s+1):
            a=A[n-i]
            if j-a>0:
                dp[i][j]=(dp[i-1][j]+dp[i-1][j-a])%mod
            elif j==a:
                dp[i][j]=(dp[i-1][j]+i)%mod
            else:
                dp[i][j]=dp[i-1][j]
    ans=0
    for i in range(1,n+1):
        a=A[i-1]
        if s>a:
            ans=(ans+dp[n-i][s-a]*i)%mod
        elif s==a:
            ans=(ans+(n-i+1)*i)%mod
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

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

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

"""
dpなのはそうだろう
普通に行けば、ナップサックdpでいける
S以下のみしか保持しなくていい

始点を保持してしまうと、Sになった時に…？
始点より左にあるやつの個数の和を記録しておけばいい！

連続してなくていいから
"""

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

for i in range(N):

    ndp = []
    for ll in dp:
        ndp.append(ll)

    if A[i] <= S:
        ndp[A[i]] += i+1
        ndp[A[i]] %= mod

    for j in range(S):

        if j+A[i] <= S:
            ndp[j+A[i]] += dp[j]
            ndp[j+A[i]] %= mod

    ans += ndp[S]
    ans %= mod

    dp = ndp

    #print (dp)

    
print (ans)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, S = na()
a = na()
mod = 998244353

def go(f, t, step, a, S):
    dp = [0] * (S+1)
    dp[0] = 1
    ret = [0] * (S+1)
    while f != t:
        for i in range(S, a[f]-1, -1):
            dp[i] += dp[i-a[f]]
            if dp[i] >= mod:
                dp[i] -= mod
        for i in range(S+1):
            ret[i] += dp[i]
        f += step
    for i in range(S+1):
        ret[i] %= mod
    return ret

def dfs(l, r, a, S):
    if r-l <= 1:
        return 1 if a[l] == S else 0
    h = (l+r)//2
    L = go(h-1, l-1, -1, a, S)
    R = go(h, r, 1, a, S)
    # print(l, r, L, R)
    return sum(L[i] * R[S-i] for i in range(S+1)) + dfs(l, h, a, S) + dfs(h, r, a, S)

print(dfs(0, n, a, S) % mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache(maxsize=None)
def count(i, s, hasL, hasR):
    global n, a
    if i == 0:
        return s == 0 and hasL
    else:
        return (
            count(i - 1, s, hasL, hasR)
            + (count(i - 1, s - a[i], False, True) * (n - i + 1) % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * (n - i + 1) % M * i % M if not hasR and a[i] <= s else 0)
            + (count(i - 1, s - a[i], True, True) * i % M if hasR and not hasL and a[i] <= s else 0)
            + (count(i - 1, s - a[i], False, True) if hasR and not hasL and a[i] <= s else 0)            
        ) % M

print(count(n, s, False, False))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
import sys
from functools import lru_cache
input = lambda: sys.stdin.readline().strip()
n, s = [int(x) for x in input().split()]
a = [0, *(int(x) for x in input().split())]
M = 998244353
@lru_cache
def count(i, s, hasL, hasR):
    global n, a
    if i == 0:
        return s == 0 and hasL
    else:
        return sum([
            count(i - 1, s, hasL, hasR),
            count(i - 1, s - a[i], False, True) * (n - i + 1) % M if not hasR and a[i] <= s else 0,
            count(i - 1, s - a[i], True, True) * (n - i + 1) % M * i % M if not hasR and a[i] <= s else 0,
            count(i - 1, s - a[i], True, True) * i % M if hasR and not hasL and a[i] <= s else 0,
            count(i - 1, s - a[i], False, True) if hasR and not hasL and a[i] <= s else 0            
        ]) % M

print(count(n, s, False, False))

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
P = 998244353
f = [[[0 for _ in range(S+1)] for _ in range(N)] for _ in range(N)]

for LR in range(N):
    f[LR][LR][0] = 1
    f[LR][LR][A[LR]] = 1
for L in range(N):
    for R in range(L+1, N):
        a = A[R]
        for s in range(a):
            f[L][R][s] = f[L][R - 1][s]
        for s in range(a, S+1):
            f[L][R][s] = f[L][R-1][s] + f[L][R-1][s-a]

ans = 0
for L in range(N):
    for R in range(L, N):
        ans += f[L][R][S]
print(ans)

Submission status: Runtime Error

Solution code:
import sys
MOD = 998244353
def main():
    input = sys.stdin.readline
    N, S = map(int, input().split())
    *A, = map(int, input().split())
    A = [0] + A
    dp = [[0] * 3 for __ in range(S + 5)]
    dp[0][0] = 1
    for i in range(1, N + 1):
        for s in range(S, -1, -1):
            ps = s - A[i]
            dp[s][0] = (dp[s][0] + dp[s][0]) % MOD
            dp[s][1] = (dp[s][1] + dp[s][0]) % MOD
            dp[s][1] = (dp[s][1] + dp[s][1]) % MOD
            dp[s][2] = (dp[s][2] + dp[s][0]) % MOD
            dp[s][2] = (dp[s][2] + dp[s][1]) % MOD
            dp[s][2] = (dp[s][2] + dp[s][2]) % MOD
            if ps >= 0:
                dp[s][1] = (dp[s][1] + dp[ps][0]) % MOD
                dp[s][1] = (dp[s][1] + dp[ps][1]) % MOD
                dp[s][2] = (dp[s][2] + dp[ps][0]) % MOD
                dp[s][2] = (dp[s][2] + dp[ps][1]) % MOD

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

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
D = {0: [[-1, -1]]}
for i in range(N):
    L = [[j, D[j]] for j in D]
    L.sort(reverse=True)
    for jn, j in enumerate(L):
        if j[0]+A[i] <= S:
            for kn, k in enumerate(j[1]):
                if j[0]+A[i] in D:
                    D[j[0]+A[i]].append([(j[0]>0)*k[0]+(j[0]==0)*i, i])
                else:
                    D[j[0]+A[i]] = [[(j[0]>0)*k[0]+(j[0]==0)*i, i]]
p = 0
for i in D[S]:
    p += (i[0] + 1) * (N - i[1])
print(p)

Submission status: Runtime Error

Solution code:
def main():
    MOD = 998244353

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

    dp = [0] * (S + 1)

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

    print(ans)


if __name__ == '__main__':
    main()

#             dp[i + 1][s][0] = (dp[i + 1][s][0] + dp[i][s][0]) % MOD
#             dp[i + 1][s][1] = (dp[i + 1][s][1]
#                                + dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD
#             dp[i + 1][s][2] = (dp[i + 1][s][2]
#                                + dp[i][s][2] +
#                                dp[i][s][1] + (dp[i][s - x][1] if s - x >= 0 else 0)
#                                + dp[i][s][0] + (dp[i][s - x][0] if s - x >= 0 else 0)) % MOD

#     for i, x in enumerate(A):
#         dp[i + 1][0][0] = dp[i][0][0]
#         for s in range(S, -1, -1):
#             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
#
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#         dp[i + 1][0][0] = dp[i][0][0]
#         dp[i + 1][0][1] = (dp[i][0][1] + dp[i][0][0]) % MOD
#         dp[i + 1][0][2] = (dp[i][0][2] + dp[i][0][1] + dp[i][0][0]) % MOD
#         for s in range(S, 0, -1):
#             dp[i + 1][s][1] = dp[i][s][1] % MOD
#             dp[i + 1][s][2] = (dp[i][s][2] + dp[i][s][1]) % MOD
#             if s - x >= 0:
#                 v = dp[i][s - x][1] + dp[i][s - x][0]
#                 dp[i + 1][s][1] = (dp[i + 1][s][1] + v) % MOD
#                 dp[i + 1][s][2] = (dp[i + 1][s][2] + v) % MOD

#     for x in A:
#         for s in range(S, 0, -1):
#             dp[s][1] += dp[s][0]
#             if s - x >= 0:
#                 v = dp[s - x][0] + (1 if s - x == 0 else 0)
#                 dp[s][0] += v
#                 dp[s][1] += v
#             dp[s][0] %= MOD
#             dp[s][1] %= MOD
#         dp[0][0] += 1
#         dp[0][1] += (dp[0][0] + 1)

Submission status: Runtime Error

Solution code:
import sys
from functools import lru_cache
 
#read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
def mp(arg):
  return map(int,arg.split())
n,s=reads()
a=list(reads())
mod= 998244353
@lru_cache(None)
def F(k):#ｆ１＋ｆ２＋．。。ｆｋ
  if k==1:
    res=[0]*(s+1)
    res[0]=1
    if a[0]<s+1:
      res[a[0]]=1
    return res
  res=F(k-1)
  k-=1
  for i in range(s,-1,-1):
    if i-a[k]>=0:
      res[i]+=res[i-a[k]]
        res[i]%=mod
  if a[k]<s+1:
      res[a[k]]+=1
  res[0]+=1
  return res
ans=0
for i in range(1,n+1):
  ls=F(i)
  ans+=ls[-1]
ans%=mod
print(ans)

Submission status: Runtime Error

Solution code:
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: Runtime Error

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]
            dp[i+1][j+A[i]] %= MOD
        elif j==0:
            dp[i+1][A[i]] += i+1
            dp[i+1][A[i]] %= MOD
        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: Runtime Error

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:
            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: Runtime Error

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

Submission status: Runtime Error

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(21)]
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: Runtime Error

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

MOD = 998244353
dp = [[0]*(S+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)

Submission status: Runtime Error

Solution code:
import numba

@numba.jit
def main():
    n, s = list(map(int, input().split()))
    a = list(map(int, input().split()))
    dp = [[None] * (s+1) for _ in range(n+1)]
    M = 998244353


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

    for i in range(1,n+1):
        for j in range(1, s+1):
            dp[i][j] = dp[i-1][j]
            if j-a[i-1]>=0:
                dp[i][j] += dp[i-1][j-a[i-1]]
            dp[i][j] %= M
    total = 0
    for i in range(n+1):
        total += dp[i][s]
    return total%M
if __name__=="__main__":
    print(main())

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*6007
ans=0
for i in range(n):
  for j in range(s,0,-1):dp[a[i]+j]+=dp[j]
  d[a[i]]+=i
  ans+=d[s]
print(ans%998244353)

Submission status: Runtime Error

Solution code:
n,s=map(int,input().split())
dp=[[0]*(s+1) for _ in range(n)]
a=list(map(int,input().split()))
if s>=a[0]:dp[0][a[0]]=1
for i in range(1,n):
  if s>=a[0]:dp[i][a[i]]=i+1
  for j in range(s+1):
    dp[i][j]+=dp[i-1][j]
    if j-a[i]>=0:dp[i][j]+=dp[i-1][j-a[i]]
print(sum(dp[i][s]for i in range(n)))

Submission status: Runtime Error

Solution code:
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*s*9
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: Runtime Error

Solution code:
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*s*5
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: Runtime Error

Solution code:
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*s*4
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: Runtime Error

Solution code:
_,s,*a=map(int,open(0).read().split())
c,i,*d=[0]*s*3
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: Runtime Error

Solution code:
m=input()
n=input()
print(m+n)
print(m-n)
print(m*n)
print(m/n)
print(m%n)

Submission status: Runtime Error

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(2 * max(A) + 1)] 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: Runtime Error

Solution code:
MOD = 998244353

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
import sys

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

# import math

# from numba import jit

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

# import matplotlib.pyplot as plt

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


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

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

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

        for si in s_appeared:
            dp[ai + 1][si] += dp[ai][si]
            dp[ai + 1][si + w] += dp[ai][si]
            s_add.add(si + w)
        s_appeared = s_appeared|s_add

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

    print(ans % 998244353)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
n,s=map(int,input().split())
t=np.zeros(s+1)
m=998244353
a=list(map(int,input().split()))
ans=0
for i in range(n):
    if a[i]<=s:
        t[a[i]:]+=t[:-a[i]]
        t[a[i]]+=i+1
    ans+=t[-1]
    ans%=m
print(int(ans))

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

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

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

Submission status: Runtime Error

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

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

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

print(dp[N][S])

Submission status: Runtime Error

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

MOD_VAL = 998244353


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# https://atcoder.jp/contests/abc159/submissions/11139734

def main():
    MOD = 998244353

    N, S = map(int, input().split())
    *a, = map(int, input().split())

    dp = [0] * (S + 1)

    ret = 0
    for i, x in enumerate(a):
        dp[0] += 1
        ret = (ret + dp[S - x] * (N - i)) % MOD
        for k in range(S - 1, x - 1, -1):
            dp[k] = (dp[k] + dp[k - x]) % MOD

    print(ret)


if __name__ == '__main__':
    main()