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 -*-

import sys

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    dp = [[[0,0,0]for _ in range(S+1)]for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0] ;dp[i+1][j][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(int(dp[N][S][2]))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin
mod = 998244353
def main():
    N,S = map(int,stdin.readline().split())
    a = list(map(int,stdin.readline().split()))
    a = np.asarray(a)
    dp = np.zeros((N+1,S+1,3))
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0] ;dp[i+1][j][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(int(dp[N][S][2]))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
mod = 998244353
def main():
    N,S = map(int,input().split())
    a = list(map(int,input().split()))
    dp = [[[0,0,0] for _ in range(S+1)]for _ in range(N+1)]
    dp[0][0][0] = 1
    for i in range(N):
        for j in range(S+1):
            dp[i+1][j][0] += dp[i][j][0] ;dp[i+1][j][0] %= mod
            dp[i+1][j][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j][1] %= mod
            dp[i+1][j][2] += dp[i][j][0]+dp[i][j][1]+dp[i][j][2];dp[i+1][j][2]%= mod
            if j+a[i] <= S:
                dp[i+1][j+a[i]][1] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][1] %= mod
                dp[i+1][j+a[i]][2] += dp[i][j][0]+dp[i][j][1];dp[i+1][j+a[i]][2] %= mod
    print(dp[N][S][2])
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.array([[[0] * 3 for _ in range(s + 1)] for _ in range(n + 1)], dtype=np.int64)
dp[0][0][0] = 1

for i, e in enumerate(a):
    dp[i+1, :, 0] += dp[i, :, 0]
    dp[i+1, :, 1] += dp[i, :, 0] + dp[i, :, 1]
    dp[i+1, :, 2] += dp[i, :, 0] + dp[i, :, 1] + dp[i, :, 2]

    dp[i+1, e:, 1] += dp[i, :-e, 0] + dp[i, :-e, 1]
    dp[i+1, e:, 2] += dp[i, :-e, 0] + dp[i, :-e, 1]

    dp[i+1, :, :] %= mod

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

for i, e in enumerate(a):
    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 + e <= s:
            dp[i+1][j+e][1] += dp[i][j][0] + dp[i][j][1]
            dp[i+1][j+e][2] += dp[i][j][0] + dp[i][j][1]

        for k in range(3):
            dp[i+1][j][k] %= mod

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

Submission status: Time Limit Exceeded

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

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

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

print(ans % MOD)

Submission status: Time Limit Exceeded

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

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

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

print(ans % MOD)

Submission status: Time Limit Exceeded

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

mod = 998244353

res = 0

#dp[i][j]:a[i]まででf(L,?) = jとなるLの合計数
dp = [[0]*3003 for i in range(n)]

for i in range(n):
    if a[i] < s:
        res = (res+dp[i-1][s-a[i]]*(n-i))%mod
    elif a[i] == s:
        res = (res+(i+1)*(n-i))%mod
    for j in range(3003):
        if j < a[i]:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j] + dp[i-1][j-a[i]]
    dp[i][a[i]] += i+1
print(res)

Submission status: Time Limit Exceeded

Solution code:
K = 32
P = 998244353
m = int(("1" * 2 + "0" * 30) * 3001, 2)
mm = 1 << K * 3001
mmm = 1 << K
pa = (1 << 30) - ((1 << 30) % P)

M = []
N, S = map(int, input().split())
A = [int(a) for a in input().split()]
s = 0
ans = 0
for a in A:
    s += 1
    s += s << a * K
    s %= mm
    s -= ((s & m) >> 30) * pa
    ans += (s >> S * K) % mmm

print(ans % P)

Submission status: Time Limit Exceeded

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

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]%MOD,dp[r-1][s][1]+dp[r-1][s-l[r]][1]%MOD] 


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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

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(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()
A = inputIL()

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(ans)

Submission status: Time Limit Exceeded

Solution code:
def f_knapsack_for_all_segments(MOD=998244353):
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    dp = [[[0] * 3 for s in range(S + 1)] for i in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for s in range(S + 1):
            # i 番の要素を採用しない場合
            dp[i + 1][s][0] += dp[i][s][0]
            dp[i + 1][s][1] += dp[i][s][0] + dp[i][s][1]
            dp[i + 1][s][2] += dp[i][s][0] + dp[i][s][1] + dp[i][s][2]
            for t in range(3):
                dp[i + 1][s][t] %= MOD

            # i 番の要素を採用できる場合
            if s + A[i] <= S:
                dp[i + 1][s + A[i]][1] += dp[i][s][0] + dp[i][s][1]
                dp[i + 1][s + A[i]][2] += dp[i][s][0] + dp[i][s][1]
                for t in range(1, 3):
                    dp[i + 1][s + A[i]][t] %= MOD
    return dp[N][S][2]

print(f_knapsack_for_all_segments())

Submission status: Time Limit Exceeded

Solution code:
def f_knapsack_for_all_segments(MOD=998244353):
    N, S = [int(i) for i in input().split()]
    A = [int(i) for i in input().split()]

    dp = [[[0] * 3 for s in range(S + 1)] for i in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for s in range(S + 1):
            # i 番の要素を採用しない場合
            dp[i + 1][s][0] += dp[i][s][0]
            dp[i + 1][s][1] += dp[i][s][0] + dp[i][s][1]
            dp[i + 1][s][2] += dp[i][s][0] + dp[i][s][1] + dp[i][s][2]
            for t in range(3):
                dp[i + 1][s][t] %= MOD

            # i 番の要素を採用できる場合
            if s + A[i] <= S:
                dp[i + 1][s + A[i]][1] += dp[i][s][0] + dp[i][s][1]
                dp[i + 1][s + A[i]][2] += dp[i][s][0] + dp[i][s][1]
                for t in range(1, 3):
                    dp[i + 1][s + A[i]][t] %= MOD
    return dp[N][S][2]

print(f_knapsack_for_all_segments())

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
def main():
    N,S= map(int,input().split())
    a_list = list(map(int,input().split()))

    # dp[i][j]: i番目までの数字を使ってjを作るときの左右の数字ペア

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


    ans=0
    pair_list = {}

    a0 = a_list[0]
    if a0<=S:
        dp[0][a0].append(0)
    if a0==S:
        pair_list[0] = [0]


    for i in range(1,N):
        a = a_list[i]
        for j in range(1,S+1):
            if j==S:
                l_list = []

                # i番目だけを使う場合
                if j==a:
                    l_list.append(i)
                pre_j = j-a
                # i-1番目以前と i番目を使う場合
                if pre_j>0:
                    l_list.extend(dp[i-1][pre_j])
                for l in l_list:
                    l+=1
                    r =i+1
                    ans+= l * (N-r+1)

            else:

                # i番目を使わない場合
                dp[i][j].extend(dp[i-1][j])

                # i番目だけを使う場合
                if j==a:
                    dp[i][j].append(i)

                # i-1番目以前と i番目を使う場合
                pre_j = j-a
                if pre_j>0:
                    dp[i][j].extend(dp[i-1][pre_j])
                
                    


                # pattern_list = dp[i-1][pre_j]
                # for p in pattern_list:
                #     left = p[0]
                #     dp[i][j].append([left,i])
    # pair_list = dp[-1][-1]
    # ans = 0

    # for i in pair_list.keys():
    #     r = i+1
    #     for j in pair_list[i]:
    #         l = j+1
    #         ans += l * (N-r+1)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,S= map(int,input().split())
a_list = list(map(int,input().split()))
# j < S に置いては、dp[i][j]: i番目までの数字を使ってjを作るときに左端の数字
dp = [[[] for _ in range(S+1)] for _ in range(N+1)]
for i in range(1,N+1):
    ai = a_list[i-1]
    for j in range(1,S):
        dpij = []
        if j == ai:
            dpij = [i]
        conj = j - ai
        if conj > 0:
            dpij += dp[i-1][conj]
        dpij += dp[i-1][j]
        dp[i][j] = dpij
            # for ii in range(1,i):
            #     dpij += dp[ii][conj]
            # dp[i][j] += dpij

j = S
ans = 0

for i in range(1,N+1):
    ai = a_list[i-1]
    dpij = []
    if ai == j:
        dpij = [i]
    conj = j - ai
    if conj > 0:    
        dpij = dp[i-1][conj]
    for l in dpij:
        ans += l * (N+1-i)
        ans = ans % 998244353

print(ans)

Submission status: Time Limit Exceeded

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

dp = [[[0]*2 for s in range(3001)] for i in range(N)]

for n in range(N):
    for s in range(3000,-1,-1):
        dp[n][s][1] = dp[n-1][s][1]
        dp[n][s][0] = dp[n-1][s][0]
        if s>A[n]:
            dp[n][s][1] += dp[n-1][s-A[n]][0]*(N-n)
            dp[n][s][0] += dp[n-1][s-A[n]][0]
        elif s==A[n]:
            dp[n][s][1] += (n+1)*(N-n)
            dp[n][s][0] += n+1
        dp[n][s][1] %= mod
        dp[n][s][0] %= mod

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

Submission status: Time Limit Exceeded

Solution code:
N,S= map(int,input().split())
a_list = list(map(int,input().split()))
# j < S に置いては、dp[i][j]: i番目までの数字を使ってjを作るときに左端の数字
dp = [[[] for _ in range(S+1)] for _ in range(N+1)]
for i in range(1,N+1):
    ai = a_list[i-1]
    for j in range(1,S):
        dpij = []
        if j == ai:
            dpij = [i]
        conj = j - ai
        if conj > 0:
            dpij += dp[i-1][conj]
        dpij += dp[i-1][j]
        dp[i][j] = dpij
            # for ii in range(1,i):
            #     dpij += dp[ii][conj]
            # dp[i][j] += dpij

j = S
ans = 0

for i in range(1,N+1):
    ai = a_list[i-1]
    dpij = []
    if ai == j:
        dpij = [i]
    conj = j - ai
    if conj > 0:    
        dpij = dp[i-1][conj]
    for l in dpij:
        ans += l * (N+1-i)

print(ans)

Submission status: Time Limit Exceeded

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

# dp[i][j]: i番目までの数字を使ってjを作るときの左右の数字ペア

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

ans=0
pair_list = {}

a0 = a_list[0]
if a0<=S:
    dp[0][a0].append(0)
if a0==S:
    pair_list[0] = [0]


for i in range(1,N):
    a = a_list[i]
    for j in range(1,S+1):
        if j==S:
            l_list = []

            # i番目だけを使う場合
            if j==a:
                l_list.append(i)
            pre_j = j-a
            # i-1番目以前と i番目を使う場合
            if pre_j>0:
                l_list.extend(dp[i-1][pre_j])
            for l in l_list:
                l+=1
                r =i+1
                ans+= l * (N-r+1)

        else:

            # i番目を使わない場合
            dp[i][j].extend(dp[i-1][j])

            # i番目だけを使う場合
            if j==a:
                dp[i][j].append(i)

            # i-1番目以前と i番目を使う場合
            pre_j = j-a
            if pre_j>0:
                dp[i][j].extend(dp[i-1][pre_j])
            
                


            # pattern_list = dp[i-1][pre_j]
            # for p in pattern_list:
            #     left = p[0]
            #     dp[i][j].append([left,i])
# pair_list = dp[-1][-1]
# ans = 0

# for i in pair_list.keys():
#     r = i+1
#     for j in pair_list[i]:
#         l = j+1
#         ans += l * (N-r+1)
print(ans)

Submission status: Time Limit Exceeded

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

# dp[i][j]: i番目までの数字を使ってjを作るときの左右の数字ペア

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

ans=0
pair_list = {}

a0 = a_list[0]
if a0<=S:
    dp[0][a0].append(0)
if a0==S:
    pair_list[0] = [0]


for i in range(1,N):
    a = a_list[i]
    for j in range(1,S+1):
        if j==S:
            l_list = []
            if j==a:
                l_list.append(i)
            pre_j = j-a
            if pre_j>0:
                l_list.extend(dp[i-1][pre_j])
            for l in l_list:
                l+=1
                r =i+1
                ans+= l * (N-r+1)

        else:

            # i番目を使わない場合
            dp[i][j].extend(dp[i-1][j])

            # i番目だけを使う場合
            if j==a:
                dp[i][j].append(i)

            # i-1番目以前と i番目を使う場合
            pre_j = j-a
            if pre_j>0:
                dp[i][j].extend(dp[i-1][pre_j])
            
                


            # pattern_list = dp[i-1][pre_j]
            # for p in pattern_list:
            #     left = p[0]
            #     dp[i][j].append([left,i])
# pair_list = dp[-1][-1]
# ans = 0

# for i in pair_list.keys():
#     r = i+1
#     for j in pair_list[i]:
#         l = j+1
#         ans += l * (N-r+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,S= map(int,input().split())
a_list = list(map(int,input().split()))
# j < S に置いては、dp[i][j]: i番目までの数字を使ってjを作るときに左端の数字
dp = [[[] for _ in range(S+1)] for _ in range(N+1)]
for i in range(1,N+1):
    ai = a_list[i-1]
    for j in range(1,S):
        dpij = []
        if j == ai:
            dpij = [i]
        conj = j - ai
        if conj > 0:
            dpij += dp[i-1][conj]
        dpij += dp[i-1][j]
        dp[i][j] = dpij
            # for ii in range(1,i):
            #     dpij += dp[ii][conj]
            # dp[i][j] += dpij

j = S
for i in range(N+1):
    ai = a_list[i-1]
    dpij = []
    if ai == j:
        dpij = [i]
    conj = j - ai
    if conj > 0:    
        dpij = dp[i-1][conj]
    dp[i][j] = dpij 

# li = []
# for i in range(1,N+1):
#     temp = [(k,i) for k in dp[i][S]]
#     li += temp

# # print(li)

# ans = 0
# for l,r in li:
#     ans += l * (N+1-r)
# print(ans)

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

Submission status: Time Limit Exceeded

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

# dp[i][j]: i番目までの数字を使ってjを作るときの左右の数字ペア

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

def f(pair):
    l = pair[0] + 1
    r = pair[1] + 1
    return l * (N-r+1)

ans=0
pair_list = {}

a0 = a_list[0]
if a0<=S:
    dp[0][a0].append(0)
if a0==S:
    pair_list[0] = [0]



for i in range(1,N):
    a = a_list[i]
    for j in range(1,S+1):
        tmp = []

        # i番目を使わない場合
        dp[i][j].extend(dp[i-1][j])

        # i番目だけを使う場合
        if j==a:
            dp[i][j].append(i)
            tmp.append(i)

        # i-1番目以前と i番目を使う場合
        pre_j = j-a
        if pre_j>0:
            dp[i][j].extend(dp[i-1][pre_j])
            tmp.extend(dp[i-1][pre_j])
        if j==S:
            pair_list[i] = tmp


            # pattern_list = dp[i-1][pre_j]
            # for p in pattern_list:
            #     left = p[0]
            #     dp[i][j].append([left,i])
# pair_list = dp[-1][-1]
# ans = 0

for i in pair_list.keys():
    r = i+1
    for j in pair_list[i]:
        l = j+1
        ans += l * (N-r+1)
print(ans)

Submission status: Time Limit Exceeded

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

# dp[i][j]: i番目までの数字を使ってjを作るときの左右の数字ペア

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

def f(pair):
    l = pair[0] + 1
    r = pair[1] + 1
    return l * (N-r+1)

ans=0
pair_list = {}

a0 = a_list[0]
if a0<=S:
    dp[0][a0].append(0)
if a0==S:
    pair_list[0] = [0]



for i in range(1,N):
    a = a_list[i]
    for j in range(1,S+1):
        tmp = []

        # i番目を使わない場合
        dp[i][j].extend(dp[i-1][j])

        # i番目だけを使う場合
        if j==a:
            dp[i][j].append(i)
            tmp.append(i)

        # i-1番目以前と i番目を使う場合
        pre_j = j-a
        if pre_j>0:
            dp[i][j].extend(dp[i-1][pre_j])
            tmp.extend(dp[i-1][pre_j])
        if j==S:
            pair_list[i] = tmp


            # pattern_list = dp[i-1][pre_j]
            # for p in pattern_list:
            #     left = p[0]
            #     dp[i][j].append([left,i])
# pair_list = dp[-1][-1]
# ans = 0

for i in pair_list.keys():
    r = i+1
    for j in pair_list[i]:
        l = j+1
        ans += l * (N-r+1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,S= map(int,input().split())
a_list = list(map(int,input().split()))
# j < S に置いては、dp[i][j]: i番目までの数字を使ってjを作るときに左端の数字
dp = [[[] for _ in range(S+1)] for _ in range(N+1)]
for i in range(1,N+1):
    ai = a_list[i-1]
    for j in range(1,S):
        dpij = []
        if j == ai:
            dpij = [i]
        conj = j - ai
        if conj > 0:
            dpij += dp[i-1][conj]
        dpij += dp[i-1][j]
        dp[i][j] = dpij
            # for ii in range(1,i):
            #     dpij += dp[ii][conj]
            # dp[i][j] += dpij

j = S
for i in range(N+1):
    ai = a_list[i-1]
    dpij = []
    if ai == j:
        dpij = [i]
    conj = j - ai
    if conj > 0:    
        dpij = dp[i-1][conj]
    dp[i][j] = dpij 

li = []
for i in range(1,N+1):
    temp = [(k,i) for k in dp[i][S]]
    li += temp

# print(li)

ans = 0
for l,r in li:
    ans += l * (N+1-r)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,S= map(int,input().split())
a_list = list(map(int,input().split()))
# dp[i][j]: i番目までの数字を使ってjを作るときに左端の数字
dp = [[[] for _ in range(S+1)] for _ in range(N+1)]
for i in range(1,N+1):
    ai = a_list[i-1]
    for j in range(1,S+1):
        if j == ai:
            dp[i][j] = [i]
        conj = j - ai
        if conj > 0:
            dpij = []
            for ii in range(1,i):
                dpij += dp[ii][conj]
            dp[i][j] += dpij
        
li = []
for i in range(1,N+1):
    temp = [(k,i) for k in dp[i][S]]
    li += temp

# print(li)

ans = 0
for l,r in li:
    ans += l * (N+1-r)
print(ans)

Submission status: Time Limit Exceeded

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

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

dp = [[[0, 0, 0] for _ in range(s+1)] for _ in range(n+1)]
for i in range(n):
    dp[0][0][0] = 1
    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[n][s][2] % p)

Submission status: Time Limit Exceeded

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

dp = [[[0, 0, 0] for _ in range(s+1)] for _ in range(n+1)]
for i in range(n):
    dp[0][0][0] = 1
    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[n][s][2] % p)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]
n, s = map(int, input().split())
a = list(map(int, input().split()))
MOD = 998244353
dp = [0 for _ in range(3001)]
dp[0] = 1
ans = 0
for i in range(n):
	for j in range(s, a[i]-1, -1):
		dp[j] += dp[j-a[i]]
		dp[j] %= MOD
	dp[a[i]] += i
	dp[a[i]] %= MOD
	ans += dp[s]
	ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

# dp[i][j]: i番目までの数字を使ってjを作るときの左右の数字ペア

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

a0 = a_list[0]
if a0<=S:
    dp[0][a0].append([0,0])

for i in range(1,N):
    a = a_list[i]
    for j in range(1,S+1):
        
        # i番目を使わない場合
        dp[i][j] = dp[i-1][j].copy()

        # i番目だけを使う場合
        if j==a:
            dp[i][j].append([i,i])

        # i-1番目以前と i番目を使う場合
        pre_j = j-a
        if pre_j>0:
            pattern_list = dp[i-1][pre_j]
            for p in pattern_list:
                left = p[0]
                dp[i][j].append([left,i])
pair_list = dp[-1][-1]
ans = 0

for pair in pair_list:
    l = pair[0] + 1
    r = pair[1] + 1
    ans += l * (N-r+1)
print(ans)

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=[[0]*(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
  elif a==s:
    B[i+1][a]+=(i+1)*(n-i)
  for j in range(s+1):
    if j<=s:
      B[i+1][j]+=B[i][j]
    if 0<=j-a and j<s:
      B[i+1][j]+=B[i][j-a]
    if 0<=j-a and j==s:
      B[i+1][j]+=B[i][j-a]*(n-i)
    B[i+1][j]%=mod
print(B[n][s])