Problem:


Score : 100 points

Problem Statement

There are N children, numbered 1, 2, \ldots, N.

They have decided to share K candies among themselves.
Here, for each i (1 \leq i \leq N), Child i must receive between 0 and a_i candies (inclusive).
Also, no candies should be left over.

Find the number of ways for them to share candies, modulo 10^9 + 7.
Here, two ways are said to be different when there exists a child who receives a different number of candies.

Constraints

All values in input are integers.

1 \leq N \leq 100

0 \leq K \leq 10^5

0 \leq a_i \leq K

Input

Input is given from Standard Input in the following format:

N K
a_1 a_2 \ldots a_N

Output

Print the number of ways for the children to share candies, modulo 10^9 + 7.

Sample Input 1

3 4
1 2 3

Sample Output 1

5

There are five ways for the children to share candies, as follows:

(0, 1, 3)

(0, 2, 2)

(1, 0, 3)

(1, 1, 2)

(1, 2, 1)

Here, in each sequence, the i-th element represents the number of candies that Child i receives.

Sample Input 2

1 10
9

Sample Output 2

0

There may be no ways for the children to share candies.

Sample Input 3

2 0
0 0

Sample Output 3

1

There is one way for the children to share candies, as follows:

(0, 0)

Sample Input 4

4 100000
100000 100000 100000 100000

Sample Output 4

665683269

Be sure to print the answer modulo 10^9 + 7.



Sample input:
3 4
1 2 3


Sample output:
5

Submission status: Accepted

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.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().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): pass
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 = 10 ** 9 + 7


n, k = LI()
A = LI()
dp = [0] * (k + 2)
dp[1] = 1
for i in range(n):
    dp = list(accumulate(dp))
    ndp = [0] * (k + 2)
    for j in range(k + 1):
        ndp[j + 1] = dp[j + 1] - dp[max(j - A[i], 0)]
        ndp[j + 1] %= mod
    dp = ndp


print(dp[-1])

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)

N, K = list(map(int, input().split()))
a = [0] + list(map(int, input().split()))
mod = 10**9+7

dp = [[0]*(K+1) for i in range(N+1)]
dp[0][0] = 1

for i in range(1,N+1):
    s = list(itertools.accumulate(dp[i - 1]))
    for k in range(K+1):
        m = max(0, k-a[i])
        if m > 0:
            dp[i][k] = ((s[k] % mod) - (s[m-1] % mod)) % mod
        else:
            dp[i][k] = s[k] % mod

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def pprint(M):
	for row in M:
		print(row)
	print("~~~")

def main():
	MOD = 10**9 + 7
	n, k = rli()
	A = list(rli())
	dp = [[0 for __ in range(k+1)] for _ in range(n)]
	psums = [[0 for __ in range(k+1)] for _ in range(n)]
	for c in range(min(k+1, A[0] + 1)):
		dp[0][c] = 1
	psums[0][0] = dp[0][0]
	for c in range(1, k+1):
		psums[0][c] = dp[0][c] + psums[0][c-1]
		psums[0][c] %= MOD
	for r in range(1, n):
		for c in range(k+1):
			cutoff = c - A[r] - 1
			dp[r][c] = psums[r-1][c] - (psums[r-1][cutoff] if cutoff >= 0 else 0)
			dp[r][c] %= MOD
		psums[r][0] = dp[r][0]
		for c in range(1, k + 1):
			psums[r][c] = dp[r][c] + psums[r][c-1]
			psums[r][c] %= MOD
	print(dp[n-1][k] % MOD)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def pprint(M):
	for row in M:
		print(row)
	print("~~~")

def main():
	MOD = 10**9 + 7
	n, k = rli()
	A = list(rli())
	P = [A[0]]
	for i in range(1, len(A)):
		P.append(P[-1] + A[i])
	dp = [[0 for __ in range(k+1)] for _ in range(n)]
	psums = [[0 for __ in range(k+1)] for _ in range(n)]
	for c in range(min(k+1, A[0] + 1)):
		dp[0][c] = 1
	psums[0][0] = dp[0][0]
	for c in range(1, k+1):
		psums[0][c] = dp[0][c] + psums[0][c-1]
		psums[0][c] %= MOD
	for r in range(1, n):
		for c in range(min(k + 1, P[r] + 1)):
			cutoff = c - A[r] - 1
			dp[r][c] = psums[r-1][c] - (psums[r-1][cutoff] if cutoff >= 0 else 0)
			dp[r][c] %= MOD
		psums[r][0] = dp[r][0]
		for c in range(1, k + 1):
			psums[r][c] = dp[r][c] + psums[r][c-1]
			psums[r][c] %= MOD
	print(dp[n-1][k] % MOD)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from sys import stdin
mod = 10**9+7
n,k = map(int,stdin.readline().split())
arr = list(map(int,stdin.readline().split()))
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    lst = [0]
    for j in range(k+1):
        lst.append((lst[-1]+dp[i-1][j])%mod)
        dp[i][j] = (lst[j+1]-lst[max(0,j-arr[i-1])])%mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def solve():
  N, K = map(int, input().split())
  A = list(map(int, input().split()))
  mod = 10**9+7
  dp = [[0]*(K+2) for _ in range(N+1)]
  dp[0] = [0]+[1]*(K+1)
  for n in range(1,N+1):
    for k in range(1,K+2):
      dp[n][k] = (dp[n-1][k]-dp[n-1][max(0,k-A[n-1]-1)]+dp[n][k-1])%mod
  ans = (dp[-1][-1]-dp[-1][-2])%mod
  return ans
print(solve())

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
arr=list(map(int,input().split()))
dp=[[0]*(k+1) for _ in range(n+1)]
dp[0][0]=1
acum=[1]*(k+2)
acum[0]=0
for i in range(n):
  tmp=[0]
  for j in range(k+1):
    dp[i+1][j]=acum[j+1]-acum[max(0,j-arr[i])]
    dp[i+1][j]%=mod
    tmp.append((tmp[-1]+dp[i+1][j])%mod)
  acum=tmp
print(dp[-1][k]%mod)

Submission status: Accepted

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, k = ns()
    a = na()

    dp = [[0 for _ in range(k + 1)] for __ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1

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

    print(dp[n][k])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


def main():
    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    A = [0] +a
    a_max = max(A)
    dp = [[0] * (K + 1) for _ in range(N + 1)] # dp[i][j] i:既に配った数 j :番目の子供     10^7なので辛い
    mod = 10**9+7
    accum=[0] *(K+2)
    dp[0][0]=1
    for i in range(1,N): # i さん 1からN１−１さんまで
        lim = A[i] # iさんの上限
        count =0
        for t in range(K+1):
            count +=dp[i-1][t]
            accum[t+1] = count

        for j in range(K+1): # 総数
            dp[i][j] =accum[j+1] -accum[max(j-lim,0)]
            dp[i][j] %=mod


    ans =0
    for i in range(0,A[-1]+1):
        ans +=dp[N-1][K-i]
        ans %=mod

    print(ans)









if __name__ == "__main__":
    main()

Submission status: Accepted

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

n, k = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7

D = [[0] * (k+2) for i in range(n+1)]
D[0][k] = 1
for i in range(1, n+1):
    for j in range(k+1):
        D[i][max(0, j-A[i-1])] = (D[i][max(0, j-A[i-1])] + D[i-1][j]) % mod
        D[i][j+1] = (D[i][j+1] - D[i-1][j]) % mod
    for j in range(1, k+2):
        D[i][j] = (D[i][j] + D[i][j-1]) % mod
print(D[-1][0])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))

mod=10**9+7
dp=[[0]*(K+1) for i in range(N+1)]
dp[0][0]=1

for i in range(N):
  acc=[0]*(K+2)
  for j in range(K+1):
    acc[j+1]=acc[j]+dp[i][j]
    acc[j+1]%=mod
  for j in range(K+1):
    dp[i+1][j]=acc[j+1]-acc[max(0,j-a[i])]
    dp[i+1][j]%=mod
print(dp[N][K])

Submission status: Accepted

Solution code:

def resolve():
    MOD = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    dp = [[0]*(K+1) for _ in range(N+1)]
    # init 0個配る状態は1通り
    for i in range(N+1):
        dp[i][0] = 1

    for i in range(N):
        cum = [0]*(K+2)
        for j in range(K + 1):
            cum[j+1] = (cum[j] + dp[i][j]) % MOD
        for j in range(K+1):
            idx = max(0, j - A[i])
            dp[i+1][j] = cum[j+1] - cum[idx]
            dp[i + 1][j] = (dp[i+1][j]+MOD)%MOD

    print(dp[N][K])

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

def resolve():
    MOD = 10**9+7
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    dp = [[0]*(K+1) for _ in range(N+1)]
    # init 0個配る状態は1通り
    for i in range(N+1):
        dp[i][0] = 1

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

    print(dp[N][K])


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

N,K = map(int, readline().split())
A = list(map(int,readline().split()))
DIV = 10 ** 9 + 7

# dp[i][j] : i人目までにj個配るときの場合の数
# dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + ... + dp[i - 1][j - A[i - 1]]
# j に j - 1を代入
# dp[i][j - 1] = dp[i - 1][j - 1] + dp[i - 1][j - 2] + ... + dp[i - 1][j - A[i - 1] - 1]
# 上から下を引く
# dp[i][j] - dp[i][j - 1] = dp[i - 1][j] - dp[i - 1][j - A[i - 1] - 1]
# dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - Ai-1 - 1]

dp = [[0] * (K + 1) for i in range(N + 1)]
for i in range(N + 1):
  dp[i][0] = 1 # 0個配る方法は常に1通り
  
for i in range(1, N + 1):
  for j in range(1, K + 1):
    if j - A[i - 1] - 1 >= 0: # j個配れる場合 (j >= A[i - 1] + 1)
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - A[i - 1] - 1]) % DIV
    else:
      dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % DIV
      
print(dp[N][K])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

# from collections import defaultdict
# from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, K, XS):
    table = [0] * (K + 1)
    for i in range(XS[0] + 1):
        table[i] = 1

    for i in range(1, N):
        v = 0
        newtable = [0] * (K + 1)
        accum = [0] * (K + 1)
        acc = 0
        for j in range(K + 1):
            acc += table[j]
            accum[j] = acc

        # debug(": table", table)
        # debug(": accum", accum)
        for j in range(K + 1):
            # v = 0
            # for k in range(XS[i] + 1):
            #     if j - k < 0:
            #         break
            #     v += table[j - k]
            #     v %= MOD
            v = accum[j]
            k = j - XS[i] - 1
            if k >= 0:
                v -= accum[k]

            newtable[j] = v % MOD
        table = newtable

    return table[K]


def main():
    # parse input
    N, K = map(int, input().split())
    XS = list(map(int, input().split()))

    print(solve(N, K, XS))


# tests
T1 = """
3 4
1 2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5
    """


T2 = """
1 10
9
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    0
    """


T3 = """
2 0
0 0
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    1
    """


T4 = """
4 100000
100000 100000 100000 100000
"""


# def test_T4():
#     """
#     >>> as_input(T4)
#     >>> main()
#     """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
lst = list(map(int, input().split()))

ans = 0
MOD = 10**9 + 7
dp = [[0] * (k+1) for _ in range(n+1)]
dp[0][0] = 1

for i in range(n):
    sums = [0] * (k+2)
    for j in range(k+1): #|累積和
        sums[j+1] = sums[j] + dp[i][j]
        sums[j+1] %= MOD
    for j in range(k+1):
        dp[i+1][j] = sums[j+1] - sums[max(0, j-lst[i])]
        dp[i+1][j] %= MOD #累積和を利用した区間和
print(dp[n][k])

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N, K = na()
a_array = na()
mod = 10 ** 9 + 7

ans = [[0] * (K+1) for _ in range(N)]
total = [[0] * (K+1) for _ in range(N)]

for i in range(a_array[0]+1):
    ans[0][i] = 1
for i in range(K+1):
    total[0][i] = min(i + 1, a_array[0] + 1)


for i in range(1, N):
    for j in range(K+1):
        if j - a_array[i] > 0:
            ans[i][j] = (total[i-1][j] + mod - total[i-1]
                         [j-a_array[i]-1]) % mod
        else:
            ans[i][j] = total[i-1][j]
        if j == 0:
            total[i][j] = ans[i][j]
        else:
            total[i][j] = (total[i][j-1] + ans[i][j]) % mod


print(ans[-1][-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0 for i in range(K+10)] for j in range(N+10)]
mod = int(1e9) + 7
dp[0][0] = 1
for i in range(N):
    pSum = [0 for _ in range(K+10)]
    for j in range(K+1):
        pSum[j + 1] = (pSum[j] + dp[i][j]) % mod
    for j in range(K+1):
        if i >= len(a):
            continue
        dp[i+1][j] = (pSum[j+1] - pSum[max(0, j - a[i])]) % mod
print(dp[N][K])

Submission status: Accepted

Solution code:
n,k = map(int,input().split())

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

dp = [0] * (k+1)
minimo = [1] * (k+2)

mod = 1e9 + 7

dp[0] = 1
minimo[0] = 0

for i in range(1, n + 1):
    soma = [0] * (k+2)

    for j in range(k+1):
        dp[j] = (minimo[j+1] - minimo[max(0, j - min(k,candies[i-1]))]) % mod
        soma[j+1] = (soma[j] + dp[j]) % mod

    minimo = soma

print(int(dp[k]))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

dp = [0]*(k+1)
cum = [1]*(k+2)
M = 10**9+7
dp[0] = 1
cum[0] = 0
for i in range(1,n+1):
    current = [0]*(k+2)
    for j in range(k+1):
        dp[j] = (cum[j+1] - cum[max(0, j-min(k,a[i-1]))]) % M
        current[j+1] = (current[j] + dp[j])%M
    cum = current
print(dp[k])

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


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

dp = [[0]*(k+1) for _ in range(n+1)]
cum = [1]*(k+2)
M = 10**9+7
for i in range(n+1):
    dp[i][0] = 1
cum[0] = 0
for i in range(1,n+1):
    current = [0]*(k+2)
    for j in range(k+1):
#         print(i,j,k,a[i])
        dp[i][j] = (cum[j+1] - cum[max(0, j-min(k,a[i-1]))]) % M
        current[j+1] = (current[j] + dp[i][j])%M
    cum = current
print(dp[n][k])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*a, = map(int, input().split())

dp = [[1] + [0]*K for _ in range(N)]
for k in range(1, a[0]+1):
    dp[0][k] = 1

for i in range(1, N):
    for k in range(1, K+1):
        if k - a[i] - 1 >= 0:
            dp[i][k] = dp[i][k-1] + dp[i-1][k] - dp[i-1][k-a[i]-1]
        else:
            dp[i][k] = dp[i][k-1] + dp[i-1][k]
        dp[i][k] %= 1e9+7
        
print(int(dp[-1][-1]))

Submission status: Accepted

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13
 
# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''
 

def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
 ############ ---- Input Functions ---- #######End
 # #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	start = {}
	def pre(arr):
		ans = [arr[0]]
		for i in range(1,len(arr)):
			ans.append((ans[-1] + arr[i])%mod)
		return ans
	for test in range(tests):
		[n,k] = inlt()
		a = inlt()
		dp = [[0 for j in range(k+1)] for i in range(n)]
		for i in range(0,a[0]+1):
			dp[0][i] = 1
		pre_sum = pre(dp[0])
		for i in range(1,n):
			for j in range(0,k+1):
				lower = max(j - a[i],0)
				dp[i][j] = (pre_sum[j] - pre_sum[lower] + dp[i-1][lower])%mod
			pre_sum = pre(dp[i])
		# print(dp)
		print(dp[-1][-1]) 

				





		
		


if __name__== "__main__":
	main()

Submission status: Accepted

Solution code:
from itertools import accumulate

def solve():
    MOD = 10**9 + 7

    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [0] * (K+1)
    dp[0] = 1
    for A in As:
        dp = list(accumulate(dp))
        for j, d in enumerate(dp[:K-A], start=A+1):
            dp[j] -= d
        dp = [dpi % MOD for dpi in dp]

    print(dp[K])


solve()

Submission status: Accepted

Solution code:
import sys
n,k=map(int,input().split())
a=list(map(int,input().split()))
I=10**9+7

if sum(a)<k:
    print(0)
    sys.exit()

dp=[[float("inf")]*(k+1) for _ in range(n+1)]
for p in range(k+1):
    dp[0][p]=0
    if a[0]<p:
        dp[1][p]=0
    else:
        dp[1][p]=1
for i in range(1,n):
    s=[0]*(k+2)
    for j in range(k+1):
        s[j+1]=s[j]+dp[i][j]%I
        dp[i+1][j]=s[j+1]-s[max(0,j-a[(i+1)-1])]

print(dp[n][k]%I)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[0]*(k+1)
mod=10**9+7
for i in range(0,a[0]+1):
    dp[i]=1
for i in range(1,len(a)):
    for j in range(1,k+1):
        dp[j]=(dp[j]+dp[j-1])%mod
    for j in range(k,a[i],-1):
        dp[j]=(dp[j]-dp[j-a[i]-1]+mod)%mod
print(dp[k])

Submission status: Accepted

Solution code:
MOD = 10**9+7

N, K = map(int, input().split())
a = list(map(int, input().split()))

# i 番目までに j 枚使ったときの場合の数
dp = [[0]*(K+1) for _ in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
    for j in range(1, K+1):
        dp[i-1][j] += dp[i-1][j-1]
    for j in range(K+1):
        dp[i][j] = dp[i-1][j]
        if j > a[i-1]:
            dp[i][j] -= dp[i-1][j-a[i-1]-1]
        dp[i][j] %= MOD

print((dp[N][K]+MOD)%MOD)

Submission status: Accepted

Solution code:
MOD = 10**9+7

N, K = map(int, input().split())
a = list(map(int, input().split()))

# i 番目までに j 枚使ったときの場合の数
dp = [[0]*(K+1) for _ in range(N+1)]
dp[0][0] = 1

upper = 0
for i in range(1, N+1):
    for j in range(1, K+1):
        dp[i-1][j] += dp[i-1][j-1]
    upper += a[i-1]
    for j in range(min(upper, K)+1):
        if j > a[i-1]:
            dp[i][j] = dp[i-1][j] - dp[i-1][j-a[i-1]-1]
        else:
            dp[i][j] = dp[i-1][j]
        dp[i][j] %= MOD

print((dp[N][K]+MOD)%MOD)

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
li=[int(K) for K in input().split()]
dp=[[0 for j in range(k+1)] for i in range(n+1)]
dp[0][0]=1
for b in range(1,n+1):
  dp[b][0]=1
mod=10**9+7  
for i in range(1,n+1):
  sums=[0]*(k+1)
  sums[0]=1
  for j in range(1,k+1):
    sums[j]=(sums[j-1]+dp[i-1][j])%mod
  for a in range(k+1):
    res=sums[a]
    if(a-li[i-1]-1)>=0:
      res=(res-sums[a-li[i-1]-1]+mod)%mod
    dp[i][a]=res
print(dp[n][k])

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
from functools import lru_cache
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dp=[[0]*(k+1) for j in range(n+1)]

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

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

Submission status: Accepted

Solution code:
def add(a, b):
    mod = 1e9+7
    return (a+b) % mod
def subtract(a, b):
    mod = 1e9+7
    return (a-b) % mod

n, k = [int(x) for x in input().split()]

arr = [int(x) for x in input().split()]

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

fake = [0 for _ in range(k+2)]

dp[0] = 1

for num in arr:
    #new_dp = [dp[i] for i in range(k+1)]
    for i in range(k+1):
        temp = dp[i]
        L = i
        R = min(i+num, k)
        fake[L] = add(fake[L], temp)
        fake[R+1] = subtract(fake[R+1], temp)
        #for i in range(L, R+1):
        #    new_dp[i] += temp
        #for use in range(1, num+1):
        #    if i+use <= k:
        #        new_dp[i+use] += temp
    pref_sum = 0
    #print(fake)
    for i in range(k+1):
        pref_sum = add(pref_sum, fake[i])
        dp[i] = pref_sum
        fake[i] = 0
    #dp = new_dp

print(int(dp[k]))

Submission status: Accepted

Solution code:
#dp[i][j] denotes number of ways to distribute j candies among first i
l=input().split()
n=int(l[0])
k=int(l[1])
l=input().split()
li=[int(i) for i in l]
dp=[[0 for i in range(k+1)]for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
for i in range(1,k+1):
    dp[0][i]=0
pref=[0 for i in range(k+1)]
sumi=0
for i in range(k+1):
    sumi+=dp[0][i]
    pref[i]=sumi
    pref[i]%=1000000007
for i in range(1,n+1):
    for j in range(1,k+1):
        howmany=li[i-1]
        left=max(0,j-howmany)
        right=j
        if(left==0):
            dp[i][j]=pref[j]
        else:
            dp[i][j]=pref[j]-pref[left-1]
        dp[i][j]%=1000000007
    sumi=0
    for j in range(k+1):
        sumi+=dp[i][j]
        pref[j]=sumi
        pref[j]%=1000000007
print(dp[n][k])

Submission status: Accepted

Solution code:


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


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[N][K] = sum(OPT[N-1][K-i]) 0 <= i <= A[N]
    OPT[0][0] = 1
    N*K
    3 4
    1 2 3

1 0 0 0 0
1 1 0 0 0
1 2 2 1 0
1 3 5 6 5

OPT[3][1] = OPT[2][1]+OPT[2][0]
OPT[3][2] = OPT[2][2]+OPT[2][1]+OPT[2][0]
OPT[3][3] = OPT[2][3]+OPT
    """
    N, K = read_ints()
    A = read_ints()
    modulo = 10**9+7
    OPT = [[0]*(K+1) for _ in range(N+1)]
    for i in range(N+1):
        OPT[i][0] = 1
    for j in range(K+1):
        OPT[0][j] = 1
    for i in range(1, N+1):
        for j in range(1, K+1):
            OPT[i][j] += OPT[i][j-1]+OPT[i-1][j]
            if j-A[i-1]-1 >= 0:
                OPT[i][j] -= OPT[i-1][j-A[i-1]-1]
            OPT[i][j] %= modulo
    if K == 0:
        return OPT[-1][-1]
    return (OPT[-1][-1]-OPT[-1][-2])%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
from itertools import accumulate

mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())

dp = [1] + [0] * K
for a in A:
    S = list(accumulate(dp)) + [0]
    for i in range(K + 1):
        dp[i] = (S[i] - S[max(0, i - a) - 1]) % mod

print(dp[K])

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())

dp = [1] + [0] * (K + 1)
for a in A:
    for i in range(1, K + 1):
        dp[i] += dp[i - 1]
    for i in reversed(range(1, K + 1)):
        dp[i] -= dp[max(0, i - a) - 1]
        dp[i] %= mod

print(dp[K])

Submission status: Accepted

Solution code:
mod=10**9+7
N,K=map(int,input().split())
a = list(map(int,input().split()))
ans=[[0 for e in range(K+1)] for f in range(N+1)]
for e in range(K+1):
 ans[1][e]=min(e+1,a[0]+1)
if N>1:
 for i in range(2,N+1):
  ans[i][0]=1
  for j in range(1,K+1):
   ans[i][j]=ans[i][j-1]+ans[i-1][j]
   if j-a[i-1]-1>=0:
    ans[i][j]-=ans[i-1][j-a[i-1]-1]
   ans[i][j]%=mod
if K==0:
 print(ans[N][K])
else:
 print((ans[N][K]-ans[N][K-1])%mod)

Submission status: Accepted

Solution code:
large_p = 10**9 + 7
from itertools import accumulate
from itertools import chain
def main():
    n, k = map(int, input().split())
    a = tuple(map(int, input().split()))
    dp = [[0] * (k+1) for _ in range(n+1)]
    dp[0][0] = 1
    for i1 in range(n):
        accum = tuple(chain([0], accumulate(dp[i1])))
        for i2 in range(k + 1):
            t = max(0, i2 - a[i1])
            dp[i1 + 1][i2] += accum[i2+1] - accum[t] + large_p
            dp[i1 + 1][i2] %= large_p

    print(dp[n][k])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, K = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0]*(K+2) for _ in range(N+1)]
dp[0][0] = 1
MOD = 10**9+7

for i in range(N):
    for j in range(K+1):
        dp[i+1][j] += dp[i][j]
        dp[i+1][min(K, j+a[i])+1] -= dp[i][j]
        
    dp[i+1][0] %= MOD
    
    for j in range(1, K+2):
        dp[i+1][j] += dp[i+1][j-1]
        dp[i+1][j] %= MOD
    
print(dp[N][K])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n,k=map(int,input().split())
    A=list(map(int,input().split()))
    dp=[[0]*(k+1) for _ in range(n+1)]
    dp[0][0]=1
    cum=[0]*(k+2)
    mod=10**9+7
    for i in  range(1,n+1):
        cum[0]=0 #dp[i-1]のj未満の和
        for j in range(k+1):
            cum[j+1]=cum[j]+dp[i-1][j]
        for j in range(k+1):
            dp[i][j]=(cum[j+1]-cum[max(0,j-A[i-1])])%mod
    print(dp[n][k])
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from numpy import*
n,k,*a=int_(open(0).read().split())
b=[1]+[0]*k
for i in a:b[i+1:]-=copy(b[:~i]);b=cumsum(b)%(10**9+7)
print(b[k])

Submission status: Accepted

Solution code:
from numpy import*
n,k,*a=int_(open(0).read().split())
b=int_([1]+[0]*k)
for i in a:b[i+1:]-=copy(b[:~i]);b=cumsum(b)%(10**9+7)
print(b[k])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
d=[[0]*(K+2) for i in range(N+1)]
d[0]=[0]+[1]*(K+1)
m=10**9+7
for i in range(N):
    for j in range(K+1):
        d[i+1][j+1]=(d[i][j+1]-d[i][max(0,j-A[i])]+d[i+1][j])%m
print((d[-1][-1]-d[-1][-2])%m)

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    ni = i + 1
    ruiseki = [0] * (k + 1)
    pre = 0
    for j in range(k + 1):
        ruiseki[j] += pre
        ruiseki[j] += dp[i][j]
        pre = ruiseki[j]
        dp[ni][j] += ruiseki[j]
        if j - A[i] > 0:
            dp[ni][j] -= ruiseki[j - A[i] - 1]
        dp[ni][j] %= mod
print(dp[n][k])

Submission status: Accepted

Solution code:

MOD = int(1e9)+7


def main():
    n, K = map(int, input().split())
    a = list(map(int, input().split()))

    # dp[i][j] is the number of ways to distribute j candies to first i people
    dp = [[0]*(K+1) for i in range(n+1)]
    prefix = [[0]*(K+1) for i in range(n+1)]
    prefix[0] = [1]*(K+1)
    for i in range(1, n+1):
        for j in range(K+1):
            start = j - min(a[i-1], j)-1
            end = j
            dp[i][j] = (prefix[i-1][end] - \
                (prefix[i-1][start] if start >= 0 else 0))%MOD
            prefix[i][j] = (prefix[i][j-1] + dp[i][j]) % MOD

    print(dp[n][K]%MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

cs_a, cnt = [0] * n, 0
for i in range(n):
    cnt += a[i]
    cs_a[i] = cnt
dp = [[0] * (k + 1) for i in range(n + 1)]

for i in range(n + 1):
    for j in range(k + 1):
        if j == 0:
            dp[i][j] = 1
        elif (i == 0) or (j > cs_a[i - 1]):
            dp[i][j] = 0
        elif j - a[i - 1] - 1 < 0:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - a[i - 1] - 1]
        dp[i][j] %= 10 ** 9 + 7

print(dp[n][k])