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:
# import copy
# In general, DP problems can often be thought of as a decision making process, where you make some "local" decision and your state after that 
# local decision becomes some state you have previously calculated the answer for. So, when you are on a given state, you try all the local 
# decisions you can, and take the one that results in the best answer (or in this case, sum up the number for each local decision to get the 
# total count for the current state).

# Your dp state characterization is correct: dp[i][j] represents the number of ways of distributing j candies among the first i people. 
# Now, say you are trying to calculate dp[i][j]. What is the "local decision" that you must make at this state? It will just be how many 
# candies you want to give to the i'th person (in fact, deciding what to do with the i'th person is often the decision that must be made 
# when your dp state deals with "something among the first i people"). So, say you want to give the i'th person k candies, where k is 
# somewhere between 0 and min(ai, j) (we can't give them more than ai candies because of the problem constraint, and can't give them more 
# than j candies because we only have j candies). Then, we see that if we give k candies to person i, then the number of ways to do 
# that is dp[i - 1][j - k] (because we precisely want to find the number of ways to distribute j - k candies to the first i - 1 people). 
# If we sum up these numbers over all the k from 0 to min(ai, j), then we should get the count for dp[i][j].

# You'll notice, though, that this results in O(NK) states and O(K) operations per state, or O(NK2) runtime, which is too slow. 
# There is something about the state transitions that allows you to calculate the sum over all the different local decisions much faster, 
# in fact in O(1). Can you think of what to do? Hint: all of the local decisions for a given dp[i][j] recurse into a contiguous block 
# in the dp[i - 1] row.

N, K = map(int,  input().split())
A = list(map(int,  input().split()))
dp = [[0 for k in range(K+1)] for n in range(N)]
# pref = [0 for k in range(K+1)]
# sSum = [0 for n in range(N)]
# sSum[N-1] = A[N-1]
# for n in range(N-2, -1, -1):
# 	sSum[n] = sSum[n+1] + A[n]
mod = int(1e9+7)
dp[N-1][0] = 1
# pref[0] = 1
for k in range(1, K+1):
	if k > A[N-1]:
		dp[N-1][k] = 0
		# pref[k] = 0
	else:
		dp[N-1][k] = 1
		# pref[k] = 1
# print(pref)
for n in range(N-2, -1, -1):
	ans = 0
	for k in range(A[n]+1):
		ans += dp[n+1][k]%mod
		ans = ans
		dp[n][k] = ans%mod
	# print(dp)
	for k in range(A[n]+1,K+1):
		# print(n, k ,ans, dp[n+1][k], dp[n+1][k-A[n]-1])
		ans = (ans%mod + dp[n+1][k]%mod - dp[n+1][k-A[n]-1]%mod + mod)%mod
		dp[n][k] = ans%mod
	# pref = copy.deepcopy(dp[n])
# print(dp)
print(dp[0][K])

Submission status: Accepted

Solution code:
mod = 10**9+7
N, K = map(int, input().split())
a = list(map(int, input().split()))
# dp[j] := the number of ways to distribute j candies
dp = [0] * (K+1)
dp[0] = 1
for i in range(N):
    ndp = [0] * (K+1)
    ndp[0] = 1
    for j in range(1, K+1):
        ndp[j] = ndp[j-1] + dp[j]
        if j - a[i] - 1 >= 0:
            ndp[j] -= dp[j-a[i]-1]
        ndp[j] %= mod
    dp = ndp
print(dp[K])

Submission status: Accepted

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

dp = [[None] * (k + 1) for _ in range(n + 1)]
def dfs(i=0, at=k):
    if dp[i][at] is not None:
        return dp[i][at]

    if i == n:
        r = int(at == 0)
        dp[i][at] = r
        return r

    cnt = 0
    for v in range(a[i] + 1):
        if v > at:
            break
        cnt += dfs(i + 1, at - v)
    dp[i][at] = cnt
    return cnt
#
# print(dfs())
# for v in dp:
#     print(v)

def fm(array):
    return ["*" if v is None else v for v in array]

def mod(v):
    if v >= M:
        return v % M
    return v

# def addmod(a, b):
#     return mod(a + b)

# for at in range(k + 1):
for i in reversed(range(n + 1)):
    for at in range(k + 1):
        if i == n:
            dp[i][at] = int(at == 0)
            continue
        cnt = 0
        # print(*fm(dp[i]), end=" -> ")
        # for v in range(min(a[i], at) + 1):
        #     cnt += dp[i + 1][at - v]
        # dpcnt = cnt
        cnt = cs[at] - cs[at - min(a[i], at) - 1]
        dp[i][at] = mod(cnt)
        # print(*fm(dp[i]), "@", at - min(a[i], at), "~", at)
        # print(cnt, "@", at - min(a[i], at), "~", at, ":", *fm(dp[i + 1])[at - min(a[i], at):at + 1])
        # print(dpcnt, cnt)
    # cs = list(itertools.accumulate(dp[i], func=addmod)) + [0]
    cs = list(itertools.accumulate(dp[i])) + [0]
    cs = [mod(v) for v in cs]
    # print(*cs, "cs")
    # print(*dp[i], "dp")
    # print("-----")
print(dp[0][k] % M)

# for v in dp:
#     print(*fm(v))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

#solve
def solve():
    n, k = LI()
    a = LI()
    dp = [0] * (k + 1)
    acc = [1] * (k + 1)
    dp[0] = 1
    for i in range(n):
        for l in range(1, k + 1):
            dp[l] = acc[l]
            dp[l] -= acc[l - a[i] - 1] if l - a[i] > 0 else 0
            dp[l] %= mod
        for l in range(1, k + 1):
            acc[l] = acc[l - 1] + dp[l]
            acc[l] %= mod
    print(dp[-1])


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

import numpy as np

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

if K == 0:
    print (1)
    exit()

dp = np.zeros((N + 1, K + 1), dtype = np.int64)
dp[N: N + 1,:] = 1
# print (dp[N]):
for i in range(N - 1, -1, -1):
    dp[i:i + 1, :A[i] + 1] = dp[i + 1:i + 2, :A[i] + 1]
    dp[i:i + 1, A[i] + 1:] = dp[i + 1:i + 2, A[i] + 1:] - dp[i + 1:i + 2, :K - A[i]]
    # print (dp[i])
    dp[i] = np.cumsum(dp[i]) % MOD
    # print (dp[i])

print ((dp[0, K] - dp[0, K - 1]) % MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,k = map(int,input().split())
A = list(map(int,input().split()))
dp = [[0]*(k+1) for i in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
  ai = A[i-1]
  now = 0
  for ki in range(k+1):
    now += dp[i-1][ki]
    if ki - ai > 0:
      now -= dp[i-1][ki-ai-1]
    dp[i][ki] = now % mod
print(dp[n][k])
# print(dp)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']
 
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

n,k=LI()
a=LI()

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

m=0
for i in range(n):
    b=[0]*(k+2)
    for x in range(k+1):
        b[x+1]=b[x]+dp[i][x]
        b[x+1]%=mo
    m+=a[i]
    for x in range(k+1):
        dp[i+1][x]=b[x+1]-b[max(0,x-a[i])]

ans=(dp[n][k]%mo)
print(ans)

Submission status: Accepted

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

mod = 1000000007

# dp
# dp[i][j]: i人目にj個目の飴を配る時のパターン
dp = [[0] * (K + 1) for i in range(N + 1)]

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

for i in range(N):
  for j in range(K):

    if a[i] < j + 1:
      dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1] - dp[i][j - a[i]]) % mod
    else:
      dp[i + 1][j + 1] = (dp[i + 1][j] + dp[i][j + 1]) % mod
  
print(dp[N][K])

Submission status: Accepted

Solution code:
def main():
    MOD = 10**9 + 7
    N, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    dp = [[0]*(K+1) for i in range(N+1)]
    dp[0][0] = 1
    S = [0] * (K+2)
    for i in range(1, N+1):
        S[0] = 0
        for j in range(1, K+2):
            S[j] = (S[j-1] + dp[i-1][j-1]) % MOD
        # print(S)
        for j in range(K+1):
            """
            for k in range(A[i-1]+1):
                # i番目の子供がk個受け取る
                if j - k >= 0:
                    dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % MOD
            """
            dp[i][j] = (S[j+1] - S[max(0, j-A[i-1])] + MOD) % MOD
    print(dp[N][K])
    # for i in range(N+1):
    #     print(*dp[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    A = [int(a) for a in input().split()]
    mod = 7 + 10 ** 9
    DP = [[0 for j in range(K + 1)] for i in range(N)]
    for i in range(A[0] + 1): DP[0][i] = 1
    cum = [0] * (K + 2)
    for i in range(1, N):
        for j in range(1, K + 2): cum[j] = (cum[j-1] + DP[i-1][j-1]) % mod
        for j in range(K + 1): DP[i][j] = (cum[j + 1] - cum[max(0, j - A[i])]) % mod
    print(DP[N-1][K])

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    N, K = map(int, input().split())
    if K == 0:
        return 1
    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):
        a = A[i]
        for j in range(K+1):
            dp[i+1][j] += dp[i][j]
            if j+a+1 <= K:
                dp[i+1][j+a+1] -= dp[i][j]
        for j in range(K):
            dp[i+1][j+1] += dp[i+1][j]
        for j in range(K+1):
            dp[i+1][j] = dp[i+1][j] % MOD

    return dp[N][K]


print(main())

Submission status: Accepted

Solution code:
#M

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)]
for i in range(N+1):
    dp[i][0]=1


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

Submission status: Accepted

Solution code:
mod = 10**9+7

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

DP = [0]*(k+1)
DP[0] = 1

for ai in a:
    nxt = [0]*(k+1)
    # iから前ai個の和になる
    # もらうDPにして和を保持すればO(N)
    s = 0
    for i in range(k+1):
        s += DP[i]
        if i>ai:
            s -= DP[i-ai-1]
        s %= mod
        nxt[i] = s
    DP = nxt
print(DP[-1])

Submission status: Accepted

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

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

for ai in a:
    for i in range(k, -1, -1):
        dp[i] += (b[i] - b[i - min(ai, i)]) % MOD
        dp[i] %= MOD
    for i in range(1, k + 2):
        b[i] = (b[i - 1] + dp[i - 1]) % MOD
        b[i] %= MOD
print(dp[-1])

Submission status: Accepted

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

# i番目までの子供でj個の飴を分け合う組み合わせ
dp = [[0 for j in range(k+1)] for i in range(n+1)]


for i in range(n+1):
    dp[i][0] = 1
MOD = 10**9 + 7

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="#":
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="#":
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    loop = S[1] + S[2]*2 + S[3]*3
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))
#    print(dp)
    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod
#    print(dp)
    ans = dp[N][K]%mod
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examM()

"""

"""

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*a, = map(int, input().split())
MOD = 10**9+7

dp = [0]*(K+1)
sums = [0]*(K+2)

dp[0] = 1

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

    for j in range(1, K+1):
        sj = max([0, j-a[i-1]])
        dp[j] = (sums[j+1]-sums[sj]+MOD) % MOD
print(dp[K])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*a, = map(int, input().split())
MOD = 10**9+7

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

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

    for j in range(1, K+1):
        sj = max([0, j-a[i-1]])
        dp[i][j] = (sums[j+1]-sums[sj]+MOD) % MOD

print(dp[N][K])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
M=10**9+7
As = list(map(int, input().split()))
dp = [[0]*(K+1)for _ in range(N+1)]
dp2 = [[1]*(K+1)for _ in range(N+1)]
dp[0][0] = 1

for i in range(1, N+1):
    for j in range(K+1):
#        print(i,j, dp[i][j-1] - dp2[i][j-1] + dp[i-1][j], j-As[i-1])
        dp[i][j] = 1 if j==0 else (dp[i][j-1] - dp2[i][j-1] + dp[i-1][j])%M
        dp2[i][j] = 0 if j-As[i-1] <0 else dp[i-1][j-As[i-1]]%M
#        dp[i][j] = sum(dp[i-1][max(0, j-As[i])...j])
#        sum(dp[i][0...j]) = sum(dp[i-1][max(0,j-As[i])...j])
#        dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... dp[i-1][max(0, j-As[i])]
#print(dp,dp2)
print(dp[N][K])

Submission status: Accepted

Solution code:
def candies(k, a):
    mod = 10 ** 9 + 7
    cur = [0] * (k + 1)
    cur[0] = 1
    prefix = cur[:]
    nxt = cur[:]
    for x in a:
        for i in range(1, k + 1):
            prefix[i] = (prefix[i - 1] + cur[i]) % mod
        for i in range(1, k + 1):
            # nxt[i] = sum(cur[(i - x if i - x >= 0 else 0):i + 1]) % mod
            nxt[i] = (prefix[i] - (prefix[i - x - 1] if i - x - 1 >= 0 else 0)) % mod
        cur, nxt = nxt, cur
    return cur[k]


def main():
    n, k = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    return candies(k, a)


print(main())

Submission status: Accepted

Solution code:
div = 10**9 + 7

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

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

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

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

Submission status: Accepted

Solution code:
def wczytaj_liste(): 
    wczytana_lista = input()
    lista_znakow = wczytana_lista.split()
    ostateczna_lista = []
    for element in lista_znakow:
        ostateczna_lista.append(int(element))
    return ostateczna_lista 

def ciasteczka(): 
    N, K = wczytaj_liste()
    max_cukierkow = wczytaj_liste()
    przed = [1]
    for dziecko in max_cukierkow:
        po = [None]* min(len(przed)+ dziecko, K+1)
        suma_kroczaca = 0
        for i in range(len(po)):
            if len(przed) > i: #trzeba dodać
                suma_kroczaca += przed[i]
            if i-dziecko-1 > -1:
                suma_kroczaca -= przed[i-dziecko-1]
            suma_kroczaca %= 10**9+7
            po[i] = suma_kroczaca
        przed = po
    if K < len(przed):
        print(przed[K])
    else:
        print(0)
    
ciasteczka()

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 10**9 + 7

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

sm = 0

for i in range(n):
    sm += a[i]
    for j in range(k+1):
        if j == 0:
            dp[i][j] = 1
            continue
        if sm < j:
            dp[i][j] = 0
        else:
            if j-1-a[i] >= 0:
                dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1-a[i]]
            else:
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
            dp[i][j] %= mod

print(dp[n-1][k])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2 * 10**5)
mod = 10 ** 9 + 7


def main():
    N, K = map(int, input().split())
    A = [int(x) for x in input().split()]
    dp = [0] * (K + 1)
    dp[0] = 1
    for i in range(N):
        acc = [0]
        for x in dp:
            acc.append((acc[-1] + x) % mod)
        dp_ = []
        for j in range(K+1):
            dp_.append((acc[j+1] - acc[max(0, j-A[i])] + mod) % mod)
        dp = dp_
    print(dp[K])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import accumulate
INF = float("inf")

MOD = 1000000007  # type: int


def solve(N: int, K: int, a: "List[int]"):

    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(1, N+1):
        acc = [0] + list(accumulate(dp[i-1]))
        for j in range(K+1):
            dp[i][j] = acc[j+1] - acc[max(j-a[i-1], 0)]
            dp[i][j] %= MOD
    print(dp[N][K])
    return


def main():

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


if __name__ == '__main__':
    main()

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
ruiseki = [0] * (k+2)
for j in range(k+1):
    ruiseki[j+1] = ruiseki[j] + dp[0][j]

for i in range(n):
    for j in range(k+1):
        dp[i+1][j] = ruiseki[j+1] - ruiseki[max(j-a[i], 0)]
        dp[i+1][j] %= MOD
    ruiseki = [0] * (k+2)
    for j in range(k+1):
        ruiseki[j+1] = ruiseki[j] + dp[i+1][j]

print(dp[n][k])