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:
# -*- coding: utf-8 -*-
N, S = map(int, input().split())
A_list = list(map(int, input().split()))

dp = [[[] for i in range(N)] for _ in range(N)]
div_num = 998244353
ans = 0
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            if A_list[i] <= S:
                dp[i][j] = [A_list[i]]
                if A_list[i] == S:
                    ans += 1
        else:
            now_num = A_list[i]
            next_dp = dp[i + 1][j]
            temp_list = [now_num]
            temp_list.extend(next_dp)
            temp_list.extend([k + now_num for k in next_dp if k + now_num <= S])
            dp[i][j] = temp_list
            ans += temp_list.count(S)
            ans %= div_num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, S = map(int, input().split())
A_list = list(map(int, input().split()))

dp = [[[] for i in range(N)] for _ in range(N)]
div_num = 998244353
ans = 0
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            if A_list[i] <= S:
                dp[i][j] = [A_list[i]]
                if A_list[i] == S:
                    ans += 1
        else:
            temp_list = [A_list[i]]
            temp_list.extend(dp[i + 1][j])
            temp_list.extend([k + A_list[i] for k in dp[i + 1][j] if k + A_list[i] <= S])
            dp[i][j] = temp_list
            ans += temp_list.count(S)
            ans %= div_num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n,s = nm()
a = nl()
mod = 998244353
ans = 0
dp = [[0]*(s+1) for i in range(n+1)]
dp[0][0] = 1
for i,v in enumerate(a):
    dp[i+1][0] = 1
    for j in range(s+1):
        dp[i+1][j] += dp[i][j]
        if j >= v: dp[i+1][j] += dp[i][j-v]
        dp[i+1][j] %= mod
    ans += dp[i+1][s]
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N, S = map(int, input().split())
A_list = list(map(int, input().split()))

dp = [[[] for i in range(N)] for _ in range(N)]
div_num = 998244353
ans = 0
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = [A_list[i]]
            if A_list[i] == S:
                ans += 1
        else:
            dp[i][j] = dp[i][i][::]
            dp[i][j].extend(dp[i + 1][j])
            dp[i][j].extend([k + A_list[i] for k in dp[i + 1][j]])
            ans += dp[i][j].count(S)
            ans %= div_num
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
for i in range(n):
	d={a[i]:1}
	if a[i]==s:
		ans+=(i+1)*(n-i)
		ans%=mod
	for j,x in enumerate(a[i+1:],i+1):
		if s-x in d:
			ans+=(i+1)*(n-j)*d[s-x]
			ans%=mod
		for y in sorted(list(d.keys()))[::-1]:
			if x+y<=s:
				d[x+y]=d.get(x+y,0)+d[y]
				d[x+y]%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353

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

dp= [[[0 for i in range(S+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
    dp[i][i-1][0] = 1
    
    
def np(L,R,S):
#    print("np",L,R,S)
    if L>R and S!=0:
        return 0
    
    elif dp[L][R][S] >0:
        return dp[L][R][S]
    else:
#        print(1,S - A[R-1]>=0)
        if S - A[R-1]>=0:
#            print(2,(dp[L][R-1][S-A[R-1]] + dp[L][R-1][S]) )
            return (np(L,R-1,S-A[R-1]) + np(L,R-1,S)) 
        else:
#            print(3,dp[L][R-1][S])
            return np(L,R-1,S)
            



ans = 0
for R in range(1,N+1):
    for L in range(1,R+1):
        
#        print("out",(L,R,S))
        k=np(L,R,S)
#        print("end",k)
        ans += k % MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,s,*a=map(int,open(0).read().split())
ans=0
mod=998244353
for i in range(n):
	d={a[i]:1}
	if a[i]==s:
		ans+=(i+1)*(n-i)
		ans%=mod
	for j,x in enumerate(a[i+1:],i+1):
		if s-x in d:
			ans+=(i+1)*(n-j)*d[s-x]
			ans%=mod
		for y in sorted(list(d.keys()))[::-1]:
			if x+y<=s:
				d[x+y]=d.get(x+y,0)+d[y]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
MOD =   998244353
DP = [[0 for p in range(S+1)]for x in range(N)]
ans = N * (A[0]==S)
if A[0]<=S:
    DP[0][A[0]] = 1
for n,a in enumerate(A):
    if n!=0:
        #もらう
        for p in range(S+1):
            DP[n][p] = DP[n-1][p]
        for p in range(a,S+1):
            DP[n][p] = DP[n-1][p] + DP[n-1][p-a]
        #初期化
        if a<=S:DP[n][a] += n+1
    ans += (DP[n][S]*(N-n))% MOD
    DP[n][S] = 0
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:


n, s = [0] * 2
a = []
mod = 998244353

def format_input(filename = None):
	global n, s
	global a
	if filename == None:
		n, s = list(map(int, input().split()))
		a = list(map(int, input().split()))

	elif filename == '__random__':
		from random import randint as rng
		n = rng(1, 3 * 10**3)
		s = rng(1, 3 * 10**3)
		a = [rng(1, 3 * 10**3) for i in range(n)]

answer = 0
def pack(start, end, room):
	global answer
	if end < n:
		if room == a[end]:
			answer += (start + 1) * (n - end)
			answer %= mod
		elif room > a[end]:
			for i in range(n-end):
				pack(start, end+i+1, room - a[end])

def get_answer():
	global answer
	for i in range(n):
		if s == a[i]:
			answer += (i + 1) * (n - i)
			answer %= mod
		elif s > a[i]:
			for j in range(n-i):
				pack(i, i+j+1, s - a[i])
	return answer

if __name__ == '__main__':
	format_input()

	ans = get_answer()
	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] * n for _ in range(3000 + 1)]

# init
dp[a[0]][0] = 1

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

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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,s = map(int,input().split())
a = list(map(int,input().split()))
mod = 998244353
rui = []
now = 0
pl = []
for i in range(n):
    now += a[i]
    rui.append(now)
l = [[0 for i in range(s)] for i in range(n)]
ans = 0
for i in range(n):
    if a[i] < s:
        l[i][a[i]] += i+1
    elif a[i] == s:
        ans += i*(n-i-1)
        ans += n
        ans %= mod
    for j in range(s):
        if i > 0:
            if l[i-1][j] > 0:
                if j+a[i] < s:
                    l[i][j+a[i]] += l[i-1][j]
                elif j+a[i] == s:
                    ans += l[i-1][j]*(n-i)
                    ans %= mod
                l[i][j] += l[i-1][j]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
    N,S = map(int, input().split())
    A = np.array(list(map(int,input().split())))


    ans = 0
    for i in range(N):
        ansi = 0
        l = np.array([0])
        for j in range(i,N):
            if A[j]>S: continue
            ansi += sum( l == (S-A[j])) 
            ans += ansi
            ans = ans%998244353
            r = l + A[j]
            r.sort()
            t = 0
            for k in range(len(r),0,-1):
                if r[k-1] <= S:
                    t = k
                    break
            l = np.hstack((l,r[:t]))
    print(ans)
    
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict

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

MOD = 998244353

dp = dict()

for i in range(N):
    dp[(i, i)] = Counter([0])

ans = 0
for m in range(1, N + 1):
    for s in range(0, N + 1 - m):
        dp[(s, s + m)] = dp[(s, s + m - 1)].copy()
        for k, v in dp[(s, s + m - 1)].items():
            if k + A[s + m - 1] <= S:
                dp[(s, s + m)][k + A[s + m - 1]] = (
                    v + dp[(s, s + m)][k + A[s + m - 1]]
                ) % MOD
        ans += dp[(s, s + m)][S]

ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 998244353
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N,S = inputIL()
l = inputIL()

dp = [[[0,0] for s in range(4000)] for r in range(4000)]

for r in range(N):
  for s in range(S):
    if s == 0:
      dp[r][s] = [1,r+2]
    if r == 0:
      if s == l[r]:
        dp[r][s] = [1,1]
      else:
        dp[r][s] = [0,0]
    else:
      dp[r][s] = [dp[r-1][s][0] + dp[r-1][s][1] + dp[r-1][s-l[r]][1],dp[r-1][s][1]+dp[r-1][s-l[r]][1]]


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

Submission status: Time Limit Exceeded

Solution code:

def solve(N, S, A):
    k = {}
    M = 998244353
    ans = 0
    s = 0
    for i, a in enumerate(A):
        if a == S:
            ans += (i + 1) * (N - i)
            ans %= M
        else:
            comp = S - a
            if comp in k:
                js = k[comp]
                for j in js:
                    ans += (j + 1) * (N - i)
                    ans %= M

            new_k = {}
            for key, value in k.items():
                if key+a < S:
                    new_k.setdefault(key+a, []).extend(value)
            if a < S:
                new_k.setdefault(a, []).append(i)

            for key, value in new_k.items():
                if key < S:
                    k.setdefault(key, []).extend(value)
    return ans % M

# print(solve(3, 4,[2,2,4]))
# print(solve(5, 8,[9,9,9,9,9]))
# print(solve(10, 10,[3,1,4,1,5,9,2,6,5,3]))

if __name__ == "__main__":
    N, S = tuple(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    print(solve(N, S, A))

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))

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

dp = [[0 for i in range(6002)]for j in range(n+1)]
ans = 0
for i in range(n):
    now = a[i]
    dp[i+1][now] = i+1
    for jj in range(s-1):
        j = jj+1
        dp[i+1][j] += dp[i][j]
        dp[i+1][j+now] += dp[i][j]
    ans += dp[i+1][s] * (n - i)
    ans %= 998244353
    #print(ans)


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] * n for _ in range(3000 + 1)]

# init
dp[a[0]][0] = 1

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

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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
B=[[[] for i in range(s+1)] for _ in range(n+1)]
ans=0
for i in range(n):
  a=A[i]
  if a<=s:
    B[i+1][a]+=[i+1]
  for j in range(s+1):
    B[i+1][j]+=B[i][j]
    if j-a>=0 and B[i][j-a]:
      B[i+1][j]+=B[i][j-a]
    
  while B[i+1][s]:
    aa=B[i+1][s].pop()
    ans=(ans+aa*(n-i))%mod
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] * n for _ in range(3000 + 1)]
dp2 = [[0] * n for _ in range(3000 + 1)]

# init
dp[a[0]][0] = 1
dp2[a[0]][0] = 1

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

        dp2[i][j] = dp2[i][j-1] + dp[i][j]


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

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

# 累積和、dp、しゃくとり
MOD = 998244353
N, S = lr()
A = lr()
# dp[k][j] kから始めた合計の個数
dp = np.array([[0] * (S+1) for _ in range(N)])
dp[:, 0] = 1
answer = 0
cur = [0] * (N)
#print(dp)
for i, a in enumerate(A):
    # iが現在地
    for j in range(i+1):
        prev = dp[j].copy()
        dp[j][a:] += prev[:-a]
        temp = dp[j][S] - cur[j]
        answer += temp * (N-i)
        cur[j] = dp[j][S]

print(answer % MOD)

Submission status: Time Limit Exceeded

Solution code:
n, s = map(int, input().split())
a = list(map(int, input().split()))
dp = [[k + 1] + [0] * s for k in range(n + 1)] #dp[i][j] : 左からi個使ってぴったりj
for i in range(1, n + 1):
    for j in range(1, s + 1):
        if j - a[i - 1] < 0:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]]
ans = 0
for i in range(1, n + 1):
    ans += dp[i][s]
    ans %= 998244353
print(ans)

Submission status: Time Limit Exceeded

Solution code:

def solve(N, S, A):
    k = {}
    M = 998244353
    ans = 0
    s = 0
    for i, a in enumerate(A):
        if a == S:
            ans += (i + 1) * (N - i)
            ans %= M
        else:
            comp = S - a
            if comp in k:
                js = k[comp]
                for j in js:
                    ans += (j + 1) * (N - i)
                    ans %= M

            new_k = {}
            for key, value in k.items():
                if key+a < S:
                    new_k.setdefault(key+a, []).extend(value)
            new_k.setdefault(a, []).append(i)

            for key, value in new_k.items():
                k.setdefault(key, []).extend(value)
    return ans % M

# print(solve(3, 4,[2,2,4]))
# print(solve(5, 8,[9,9,9,9,9]))
# print(solve(10, 10,[3,1,4,1,5,9,2,6,5,3]))

if __name__ == "__main__":
    N, S = tuple(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    print(solve(N, S, A))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,S =(int(x) for x in  input().split())
As=[int(x) for x in input().split()]
import itertools 
LRs=list(itertools.combinations_with_replacement(range(N),2))
combinations = itertools.combinations
res=0
for i in LRs:
    if i[1]==N-1:
        LR=As[i[0]:]
    else:
        LR=As[i[0]:i[1]+1]
    for x in range(len(LR)):
        res+=sum(1 for y in list(combinations(LR,x+1)) if sum(y)==S)
print(res%998244353)

Submission status: Time Limit Exceeded

Solution code:
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[[0 for i in range(S+1)] for i in range(N+1)] for k in range(N+1)]
for i in range(1,N+1):
    for j in range(i):
        dp[i][j][0] = 1
B = [0]
for i in range(1,N+1):
    for j in range(i,N+1):
        n = len(B)
        for k in range(S+1):
            dp[i][j][k] += dp[i][j-1][k]
            if k + A[j-1] <= S:
                dp[i][j][k+A[j-1]] += dp[i][j-1][k]
mod = 998244353
ans = 0
for i in range(1,N+1):
    for j in range(i,N+1):
        ans += dp[i][j][S] % mod
        ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
inpl = lambda: list(map(int,input().split()))
N, S = inpl()
A = inpl()
B = sorted([(A[i], i) for i in range(N)],reverse=True)
C = [B[i][1] for i in range(N)]
ans = 0
comb = set()
pool = [(0,None,None,0)] # node, start, end, sum
while pool:
    i, start, end, s = pool.pop()
    if i < N-1:
        pool.append((i+1,start,end,s))
    s += A[C[i]]
    if start is None:
        start = end = C[i]
    elif C[i] < start:
        start = C[i]
    elif C[i] > end:
        end = C[i]
    if s == S:
        ans += (start+1) * (N-end)
        ans %= MOD
    elif s < S and i < N-1:
        pool.append((i+1,start,end,s))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, S = list(map(int, input().split()))
A = list(map(int, input().split()))
#print(N, S)
#print(A)

#dp = [ [0] * (S+1) for i in range(len(A)+1) ]
dp = [ [0] * (len(A)+1) for i in range(S+1) ]

sum_comb = 0
for j in range(len(A), 0, -1):
  for s in range(1, S+1):
    for i in range(j, len(A)+1):
      b = 0
      if A[i-1] == s:
        b = 1
      dp[s][i] = dp[s][i-1] + dp[max(s-A[i-1], 0)][i-1] + b
  #print(dp)
  for i in range(j, len(A)+1):
    sum_comb += dp[s][i]


print(sum_comb)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
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):
        self.f = f
        self.v = None
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if self.v is None:
            self.v = n
        else:
            self.v = self.f(self.v, n) 


def f(N, S, A, L, R, exist=False):
    if S == 0:
        return [[0, L - 1]]

    SS = sum(A[L:R + 1])
    if SS < S:
        return []
    if SS == S:
        return [[L, R]]
    if L == R:
        return []

    T1 = f(N, S, A, L + 1, R, exist)
    T2 = f(N, S - A[L], A, L + 1, R, True)

    if not exist and len(T2) > 0:
        for l in T2:
            l[0] = L
    T1.extend(T2)
    return T1


def main():
    N, S = read_values()
    A = read_list()
    
    R = f(N, S, A, 0, N - 1)
    res = 0
    for l, r in R:
        res += (l + 1) * (N - r) % mod
        res %= mod
    print(res)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import fractions

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans
'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)
'''


#a = list(map(int, input().split()))

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

dp = [[0 for i in range(3002)]for j in range(n+1)]
ans = 0
for i in range(n):
    now = a[i]
    dp[i+1][now] = i+1
    for jj in range(s-1):
        j = jj+1
        dp[i+1][j] += dp[i][j]
        dp[i+1][min(3001,j+now)] += dp[i][j]
    ans += dp[i+1][s] * (n - i)
    ans %= 998244353
    #print(ans)


print(ans)

Submission status: Time Limit Exceeded

Solution code:

def solve(N, S, A):
    k = {}
    M = 998244353
    ans = 0
    s = 0
    for i, a in enumerate(A):
        if a == S:
            ans += (i + 1) * (N - i)
            ans %= M
        else:
            comp = S - a
            if comp in k:
                js = k[comp]
                for j in js:
                    ans += (j + 1) * (N - i)
                    ans %= M

            new_k = {}
            for key, value in k.items():
                new_k.setdefault(key+a, []).extend(value)
            new_k.setdefault(a, []).append(i)

            for key, value in new_k.items():
                k.setdefault(key, []).extend(value)
    return ans % M

# print(solve(3, 4,[2,2,4]))
# print(solve(5, 8,[9,9,9,9,9]))
# print(solve(10, 10,[3,1,4,1,5,9,2,6,5,3]))

if __name__ == "__main__":
    N, S = tuple(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    print(solve(N, S, A))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,s=map(int,input().split())
A=[int(i) for i in input().split()]
mod=998244353
B=[[[] for i in range(s+1)] for _ in range(n+1)]
ans=0
for i in range(n):
  a=A[i]
  if a<=s:
    B[i+1][a]+=[i+1]
  for j in range(s+1):
    B[i+1][j]+=B[i][j]
    if j-a>=0 and B[i][j-a]:
      B[i+1][j]+=B[i][j-a]
    
  while B[i+1][s]:
    aa=B[i+1][s].pop()
    ans+=aa*(n-i)
  ans%=mod
print(ans)

Submission status: Time Limit Exceeded

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

DIVIDER = 998244353

import sys
sys.setrecursionlimit(50000)

def dp(pos, price, minL, maxR):
    global N
    global S
    global DIVIDER
    if pos == N:
        if price == S:
            # calc weight here
            if minL <= maxR:
                weight = 1
                weight = (weight * (minL + 1)) % DIVIDER
                weight = (weight * (N - maxR)) % DIVIDER
                return weight
            else:
                return 0 # unreachable
        else:
            return 0
    #
    ret = 0
    ret = (ret + dp(pos + 1, price, minL, maxR)) % DIVIDER
    if price == 0:
        ret = (ret + dp(pos + 1, price + A[pos], pos, pos)) % DIVIDER
    else:
        ret = (ret + dp(pos + 1, price + A[pos], minL, pos)) % DIVIDER
    #
    return ret

print(dp(0, 0, N, 0))

Submission status: Time Limit Exceeded

Solution code:
N,S = map(int,input().split())
A = list(map(int,input().split()))
dp = [[[0 for i in range(S+1)] for i in range(N+1)] for k in range(N+1)]
for i in range(1,N+1):
    for j in range(i):
        dp[i][j][0] = 1
B = [0]
for i in range(1,N+1):
    for j in range(i,N+1):
        n = len(B)
        for k in range(n):
          if B[k] + A[j-1] not in B:
              if B[k] + A[j-1] <= S:
                  B.append(B[k]+A[j-1])
          dp[i][j][B[k]] += dp[i][j-1][B[k]]
          if B[k] + A[j-1] <= S:
              dp[i][j][B[k]+A[j-1]] += dp[i][j-1][B[k]]
mod = 998244353
ans = 0
for i in range(1,N+1):
    for j in range(i,N+1):
        ans += dp[i][j][S] % mod
        ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, S = map(int,input().split())
A = [0] + list(map(int, input().split()))
p = 998244353

dp = [[[0 for i in range(S+1)] for j in range(N+1)] for k in range(N+1)]

for j in range(N+1):
  for k in range(j+1):
    dp[k][j][0] = 1
ans = 0
for i in range(1,S+1):
  for j in range(1,N+1):
    for k in range(j+1):
      offset = dp[k][j-1][i-A[j]] if i-A[j]>-1 else 0
      dp[k][j][i] = (dp[k][j-1][i]+offset)%p
      if i == S:
        ans += dp[k][j][i]
        ans %= p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 998244353
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n,s = inpm()
    a = inpl()
    if sum(a)<s or min(a)>s:
        print(0)
        return
    past = deque()
    past.append([0,-1])
    ans = 0
    for i in range(n):
        for j in range(len(past)):
            [x,y] = past[j]
            if y == -1:
                Next = [x+a[i],i]
            else:
                Next = [x+a[i],y]
            if Next[0] == s:
                if y == -1:
                    ans += (i+1)*(n-i)
                else:
                    ans += (y+1)*(n-i)
                ans %= mod
            elif Next[0] < s:
                past.append(Next)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


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


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

ans = 0

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


print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations_with_replacement

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


def part_sum(A):
    p = 998244353
    n = len(A)
    # 初期化
    dp = [[0 for _ in range(S + 1)] for _ in range(N + 1)]
    dp[0][0] = 1

    # DP
    for i in range((len(A))):
        for j in range(S + 1):
            if A[i] <= j:
                dp[i + 1][j] = dp[i][j - A[i]] + dp[i][j] % p
            else:  
                dp[i + 1][j] = dp[i][j] % p

    return dp[n][S]


s = 0
for p, q in combinations_with_replacement(range(N), 2):
    if p == q:
        s += part_sum([AA[p]])
    else:
        s += part_sum(AA[p:q + 1])

print(s % 998244353)

Submission status: Time Limit Exceeded

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

dp  = {0:(0,0)}

for i in range(n):
  a = A[i]
  eph = {}
  for j in dp:
    if j==0:
      eph[a] = [(i+1,i+1)]
      continue
    if j+a > s:
      continue
    eph[j+a] = [(k[0],i+1) for k in dp[j]] 
  for e in eph:
    if e in dp:
      dp[e].extend(eph[e])
    else:
      dp[e] = eph[e]
if s in dp:
  cand = dp[s]
else:
  print(0)
  exit()

  
  



ans = 0
index = 0
for l,r in cand:
  ans += ((l)*(n-r+1)) % MOD
  ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, s = map(lambda i: int(i), input().split())
A = list(map(lambda i: int(i), input().split()))
cals_cache = {}
dp = [0 for i in range(s+1)]
dp[0] = 1
nonzeros = set([0])


def cals(a, dp, nonzeros):
    _nonzeros = set()
    for ind in reversed(sorted(nonzeros)):
        if ind + a > s:
            continue
        dp[ind + a] += dp[ind]
        _nonzeros.add(ind+a)
    nonzeros |= _nonzeros
    return dp[s]

ans = 0
for i in range(n):
    dp = [0 for i in range(s+1)]
    dp[0] = 1
    nonzeros = set([0])
    for j in range(i, n):
        ans += cals(A[j], dp, nonzeros)%998244353
    

print(ans)