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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, s = map(int, input().split())
    dp = [0] * (s + 1)
    res = 0
    for a in map(int, input().split()):
        dp[0] += 1
        ndp = [0] * (s + 1)
        for i in range(s + 1):
            ndp[i] += dp[i]
            if i + a <= s:
                ndp[i + a] += dp[i]
        dp = ndp
        res += dp[s]

    print(res)
resolve()

Submission status: Wrong Answer

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        dp[0] += i+1
        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        dp[0] += 1
        ans += dp[S-a]*(N-i)

        for j, x in enumerate(dp[:S-a]):
            dp[j+a] += x
    print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

    for i, a in enumerate(A):
        if a > S:
            continue
        dp[0] += 1
        ans += dp[S-a]*(N-i)

        for j in range(S-a-1, -1, -1):
            dp[j+a] += dp[j]
    print(ans % mod)


main()

Submission status: Wrong Answer

Solution code:
def main():
    N, S = map(int, input().split())
    A = list(map(int, input().split()))
    mod = 998244353
    ans = 0
    dp = [0]*S

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

main()

Submission status: Wrong Answer

Solution code:
import numpy as np
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
U = 3001

ans = 0

dp = dict()
dp[0] = np.zeros(U, dtype=np.int64)
dp[0][0] = 1

for i, a in enumerate(A, start=1):
    tmp = np.copy(dp[i-1])
    tmp[0] += 1
    tmp[a:] += dp[i - 1][:-a]
    dp[i] = tmp % mod
    ans = (ans + tmp[S] % mod)

print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, S = map(int, input().split())
A = list(map(int, input().split()))
mod = 998244353
U = 3001

ans = 0

dp = dict()
dp[0] = np.zeros(U, dtype=int)
dp[0][0] = 1

for i, a in enumerate(A, start=1):
    tmp = np.copy(dp[i-1])
    tmp[0] += 1
    tmp[a:] += dp[i - 1][:-a]
    dp[i] = tmp % mod
    ans = (ans + tmp[S] % mod)

print(ans)

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

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

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

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 998244353


def main():
    N, S = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [[0]*(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] <= S:
                dp[i+1][j+A[i]] += dp[i][j]

    # A = A[::-1]
    # dp2 = [[0]*(S+1) for _ in range(N+1)]
    # dp2[0][0] = 1
    # for i in range(N):
    #     for j in range(S+1):
    #         dp2[i+1][j] += dp2[i][j]
    #         if j + A[i] <= S:
    #             dp2[i+1][j+A[i]] += dp2[i][j]
    ans = 0
    for i in range(1, N):
        pre = dp[i][S] - dp[i-1][S]
        post = dp[i+1][S] - dp[i][S]
        ans += pre*i - post*(N-i)
    ans += (dp[N][S] - dp[N-1][S])*N
    print(ans-1)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, S = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9 + 7

dp = [0] * (S + 1)

ans = 0
for i, a in enumerate(A, start=1):
    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: Wrong Answer

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)]

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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
MOD=998244353

N,S=map(int,input().split())
A=list(map(int,input().split()))
#A=[(v,i) for i,v in enumerate(A)]
A = sorted(A)

ans=0
Q={(0,N+1,0)}
for i,a in enumerate(A):
    tmp=set()
    for val,min_i,max_i in Q:
        tmp.add((val,min_i,max_i))
        if val+a>S:
            continue
        elif val+a==S:
            min_i=min(min_i,i)
            max_i=max(max_i,i)
            r=(min_i+1)*(N-max_i)
            ans+=r
            ans%=MOD
        else:
            tmp.add((val+a,min(min_i,i),max(max_i,i)))
    Q=tmp
print(ans)

Submission status: Wrong Answer

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 l in range(N):
  r = N - l
  x = a[l]
  if x > S: continue
  for i in range(S, -1, -1):
    if i + x > S: continue
    if i + x == S:
      dp[S] += dp[i] * r
      dp[S] %= mod
    else:
      dp[i + x] += dp[i]
      dp[i + x] %= mod
  dp[x] += l + 1
  dp[x] %= mod
print(dp[-1])

Submission status: Wrong Answer

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][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 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]
    print(dp[-1][-1][2])

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
MOD = 998244353
def main():
    n, s = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [np.zeros(s+1, dtype=np.int64) for i in range(n+1)]
    ans = 0
    for i in range(n):
        if a[i] <= s:
            dp[i+1][a[i]:] = dp[i][:-a[i]]
            dp[i+1][a[i]] += i+1
        dp[i+1][:s] += dp[i][:s]
        dp[i+1][dp[i+1] >= MOD] -= MOD
        ans += dp[i+1][s] * (n-i)
#        print(dp[i+1], ans)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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(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: Wrong Answer

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

MOD = 998244353  # type: int


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


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


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

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

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

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

    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

MOD = 998244353  # type: int


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


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

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

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

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

    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

n, s = list(map(int, input().split()))
a = list(map(int, input().split()))
dp = [[None] * (s+1) for _ in range(n+1)]

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

Submission status: Wrong Answer

Solution code:
import numpy as np

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

dp=[np.zeros(s+1,dtype=np.int64) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
ans=0

for i,w in enumerate(a):
    dp[i]+=dp[i-1]
    dp[i][w:]+=dp[i-1][:-w]
    ans+=dp[i][-1]
    ans%=998244353

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 998244353
    
    dp = np.zeros(S+1,dtype=int)
    ans = 0
    
    for num in a:
        dp[0] += 1
        dp[num:] += dp[:-num].copy()
        dp %= MOD
        ans += dp[-1]
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 998244353
    
    dp = np.zeros(3000+10,dtype=int)
    ans = 0
    
    for num in a:
        dp[0] += 1
        dp[num:] += dp[:-num]
        dp %= MOD
        ans += dp[S]
        
    print(ans%MOD)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 998244353
    
    dp = np.zeros(S+1,dtype=int)
    ans = 0
    
    for num in a:
        dp[0] += 1
        dp[num:] += dp[:-num]
        ans += dp[-1]
        ans %= MOD
        
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
MOD = 998244353
n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0] * (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]
        nj = j + a[i]
        if nj > s: continue
        dp[i+1][nj] += i+1 if j == 0 else dp[i][j]
        if nj == s: dp[i+1][nj] *= n-i
        dp[i+1][nj] %= MOD

print(dp[n][s])

Submission status: Wrong Answer

Solution code:
import sys

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


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


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


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


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


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

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

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

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


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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, s = LI()
A = LI()
dp = [[0] * (s + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(s + 1):
        if j == A[i]:
            dp[i + 1][j] += i + 1
        elif j > A[i]:
            if j == s:
                dp[i + 1][j] += dp[i][j - A[i]] * (n - i)
            else:
                dp[i + 1][j] += dp[i][j - A[i]]
        dp[i + 1][j] += dp[i][j]
        dp[i + 1][j] %= mod


print(dp[n][s])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, s = LI()
A = LI()
dp = [[0] * (s + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(s + 1):
        if j == A[i]:
            dp[i + 1][j] += i + 1
        elif j > A[i]:
            if j == s:
                dp[i + 1][j] += dp[i][j - A[i]] * (n - i)
            else:
                dp[i + 1][j] += dp[i][j - A[i]]
        dp[i + 1][j] += dp[i][j]


print(dp[n][s])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


n, s = LI()
A = LI()
dp = [[0] * (s + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for j in range(s + 1):
        if j == A[i]:
            dp[i + 1][j] += i + 1
        elif j >= A[i]:
            if j == s:
                dp[i + 1][j] += dp[i][j - A[i]] * (n - i)
            else:
                dp[i + 1][j] += dp[i][j - A[i]]
        dp[i + 1][j] += dp[i][j]


print(dp[n][s])

Submission status: Wrong Answer

Solution code:

MOD = 998244353


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


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

    print(dp2[N-1][S]%MOD)

main()

Submission status: Wrong Answer

Solution code:

MOD = 998244353


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


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

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

main()

Submission status: Wrong Answer

Solution code:
MOD = 998244353

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

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

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

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

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

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

Submission status: Wrong Answer

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


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


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


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


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


n ,  k = in_ints()


a = [0] + in_list()

ans = 0

m = {}


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

    return m[(i, val)]


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

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


print(ans)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
import numpy as np
from io import StringIO
MOD = 998244353


def main():
    n, s = map(int, input().split())
    a = np.loadtxt(StringIO(input()), dtype=np.int64)
    dp = np.zeros(s + 1, dtype=np.int64)
    ans = 0
    for i in range(n):
        if a[i] > s:
            continue
        dp[0] = i + 1
        dp_next = dp.copy()
        for j in range(s + 1 - a[i]):
            dp_next[j + a[i]] += dp[j]
            dp_next[j + a[i]] %= MOD
        dp = dp_next
        ans += dp[s]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    a = LI()
    r = 0
    dp = [0] * (s+1)
    dp[0] = 1
    for i in range(n):
        ai = a[i]
        if ai > s:
            continue
        dp[s] += dp[s-ai] * (n-i)
        dp[s] %= mod2
        for j in range(s-1, ai-1, -1):
            dp[j] += dp[j-ai]
            dp[j] %= mod2
        dp[0] += 1

    return dp[-1] % mod2


print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n,s = LI()
    a = LI()
    r = 0
    dp = [0] * (s+1)
    dp[0] = 1
    for i in range(n):
        ai = a[i]
        if ai > s:
            continue
        dp[s] += dp[s-ai] * (n-i)
        dp[s] %= mod2
        if ai == s:
            dp[0] += 1
            continue
        for j in range(s-1, ai-1, -1):
            dp[j] += dp[j-ai]
            dp[j] %= mod2
        dp[0] += 1

    return dp[-1]


print(main())