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:
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 == 1:
            dp[i][j] = dp[i - 1][j] + min(a[i - 1], 1)
        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])

Submission status: Accepted

Solution code:
import numpy as np
n,k=map(int,input().split())
a=list(map(int,input().split()))
MOD=10**9+7
dp=np.zeros((n+1,k+1),dtype=np.int64)
dp[0][0]=1
cnt=1
for i in range(n):
    dp[i+1]=dp[i]
    dp[i+1][a[i-1]+1:]-=dp[i][:-(a[i-1]+1)]
    np.cumsum(dp[i+1],out=dp[i+1])
    dp[i+1]%=MOD
print(dp[n][k])

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
l=[int(x) for x in input().split()]
dp=[0 for i in range(k+1)]
dp[0]=1
M=10**9+7
for i in range(len(l)):
	p=[0]*(k+1)
	for j in range(k-1,-1,-1):
		li= j+1
		ri=j+min(l[i],k-j)+1
		if li<=ri:
			p[j+1]+=dp[j]
		if ri<=k:
			p[j+min(l[i],k-j)+1]-=dp[j]
		'''for o in range(j+1,j+min(l[i],k-j)+1):
			dp[o]+=dp[j]'''
	su=0
	for i in range(k+1):
		su=(su+p[i])%M
		dp[i]=(dp[i]+su)%M
print(dp[k]%(10**9+7))
#print(dp[0][n-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n, k = map(int, input().split())
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in map(int, input().split()):
        # accumulate dp
        S = [0] * (k + 2)
        for i in range(k + 1):
            S[i + 1] = S[i] + dp[i]
            if S[i + 1] >= MOD:
                S[i + 1] -= MOD
        # ndp[i] = dp[i - a] + ... + dp[i]
        dp = [(S[i + 1] - S[max(0, i - a)]) % MOD for i in range(k + 1)]

    print(dp[k])
resolve()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,K = LI()
a = [0]+LI()
if K == 0:
    print(1)
    exit(0)
dp = [[1] * (K+1) for _ in range(N+1)]
ac = 0
for i in range(1,N+1):
    ac += a[i]
    s = 0
    for j in range(K+1):
        s += dp[i-1][j]
        if j-a[i]-1 >= 0: s -= dp[i-1][j-a[i]-1]
        dp[i][j] = s % MOD
print((dp[-1][K]-dp[-1][K-1])%MOD)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
ns = 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):
    b = 0
    cur = [0]
    for j in range(k+1):
        b += dp[i][j] % mod
        cur.append(b)
    for j in range(k+1):
        dp[i+1][j] = (cur[j+1] - cur[max(0, j-ns[i])]) % mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
def main():

    N, K = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [[0]*(K+1) for i in range(N+1)]
    import collections
    dp[0][K] = 1
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    for i in range(1, N+1):
        tmp = 0
        q = collections.deque()
        for j in range(K, -1, -1):
            while(q):
                if q[0][0] > j:
                    t = q.popleft()
                    tmp -= t[1]
                else:
                    break
            if dp[i-1][j]:
                tmp += dp[i-1][j]
                q.append((max(j - a[i-1], 0), dp[i-1][j]))
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()

Submission status: Accepted

Solution code:
import sys
import numpy as np

M = 1000000007  # type: int


def solve(N: int, K: int, a):
    dp = np.zeros(K + 1, dtype=np.int64)
    dp[0] = 1
    for x in a:
        cm = np.cumsum(dp)
        dp = cm.copy()
        dp[x + 1 :] -= cm[: -x - 1]
        dp %= M
    return dp[K]


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 = np.array([int(next(tokens)) for _ in range(N)], dtype=np.int64)
    print(solve(N, K, a))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import copy
import sys
import numpy as np

MOD = 1000000007  # type: int


def debug(s):
    print(s)


def solve(N: int, K: int, a):
    dp = np.zeros((N + 1, K + 1), dtype=np.int64)
    dp[0, 0] = 1
    for i in range(1, N + 1):
        ai = a[i - 1]
        ndp = np.cumsum(dp[i - 1, :])
        dp[i, :] = ndp
        dp[i, ai + 1 :] -= ndp[: -ai - 1]
        dp[i, :] %= MOD
    return dp[N, K]


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 = np.array([int(next(tokens)) for _ in range(N)], dtype=np.int64)
    print(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()))

m=10**9+7

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

MOD = 10 ** 9 + 7

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

Submission status: Accepted

Solution code:
import numpy as np

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

MOD = 10 ** 9 + 7

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

Submission status: Accepted

Solution code:


def submit():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    modp = 10 ** 9 + 7
    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(n):
        for j in range(1, k + 1):
            if j - 1 - a[i] >= 0:
                dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1] - dp[i][j - 1 - a[i]]
            else:
                dp[i + 1][j] = dp[i][j] + dp[i + 1][j - 1]
            dp[i + 1][j] %= modp
    print(dp[n][k])


submit()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=100,100000
#a=[k//2]*n
mod=pow(10,9)+7
dp=[0]*(k+1) # dp[j]:j個の飴を分ける分け方。人が一人以上のとき、0個の時は明らかに1通り。0人に飴を分ける方法はないので0通り
sdp=[0]*(k+2)
for i in range(a[0]+1):#一人目だけいる時、その人が持てる飴の個数以下なら1
  dp[i]=1 
for i in range(1,n):
      # 累計和にする
      s=0
      for l in range(k+1):
            s+=dp[l]
            sdp[l+1]=s%mod
      for j in range(1,k+1):
        dp[j]=(sdp[1+j]-sdp[max(0,j-a[i])])%mod
print(dp[-1]%mod)

Submission status: Accepted

Solution code:
def main():

    from bisect import bisect_left as bl, bisect_right as br, insort
    import sys
    import heapq
    # from math import *
    from collections import defaultdict as dd, deque
    def data(): return sys.stdin.readline().strip()
    def mdata(): return list(map(int, data().split()))
    out = sys.stdout.write
    # sys.setrecursionlimit(100000)
    INF = int(1e9)
    mod = int(1e9)+7

    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

    for i in range(n):
        dpsum = [0] * (k + 2)
        for l in range(k + 1):
            dpsum[l + 1] = dpsum[l] + dp[i][l]
            dpsum[l + 1] %= mod
        for j in range(k + 1):
            dp[i + 1][j] = (dpsum[j + 1] - dpsum[max(0, j - a[i])]) % mod
    print(dp[n][k])
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[0]+list(map(int,input().split()))
P=10**9+7

#DP[i][j]=子供iまでで飴j個を分ける(1<=i<=N,0<=j<=K)
DP=[[0]*(K+1) for _ in range(N+1)]
#DP[1][j]を作る
for index1 in range(0,A[1]+1):
    DP[1][index1]=1
#DP[i][0]=1である
for index2 in range(N+1):
    DP[index2][0]=1


for i in range(2,N+1):  #2<=i<=N
    #i固定下で累積和tableを作成
    #C[index]=DP[i-1][0]+...+DP[i-1][index-1](1<=index<=K+1)
    C=[0]*(K+2)
    C[1]=DP[i-1][0]%P
    for c in range(2,K+2):
        C[c]=(C[c-1]+DP[i-1][c-1])%P
    for j in range(1,K+1):  #1<=j<=K
        DP[i][j]=(C[j+1]-C[max(0,j-A[i])])%P




print(DP[N][K]%P)


#for index3 in range(N+1):
    #string=''
    #for index4 in range(K+1):
        #string+=str(DP[index1][index2])+' '
    #print(string)

Submission status: Accepted

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

from itertools import groupby, accumulate, product, permutations, combinations

def solve(N,K,A):
    mod = 10**9+7
    dp = [[0]*(K+1) for _ in range(N+1)] #dp[i][j] i人目まででj個を分ける場合の数
    dp[0][0] = 1
    for i in range(1,N+1):
        cum = list(map(lambda x:x%mod,accumulate(dp[i-1])))
        for j in range(K+1):
            dp[i][j] = cum[j]
            k = j-A[i-1]
            if k>0:
                dp[i][j] -= cum[k-1]
    ans = dp[N][K]%mod
    return ans
print(solve(N,K,A))

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    n,k = map(int,input().split())
    candies = list(map(int,input().split()))
    dp = [[0 for i in range(k+1)] for j in range(n+1)]
    dp[0][0] = 1
    for pos in range(1,n+1):
        for used in range(k+1):
            a = candies[pos-1]
            start = used
            end = min(start+a+1,k+1)
            dp[pos][start] += dp[pos-1][start]
            if end <= k:
                dp[pos][end] -= dp[pos-1][start]

        for used in range(1,k+1):
            dp[pos][used] += dp[pos][used-1]
            dp[pos][used] %= mod


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


main()

Submission status: Accepted

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
if k > sum(a):
    print(0)
    exit()

mod = 1000000007
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(k+1):
    dp[0][i] = 0

for i in range(1,n+1):
    for j in range(1,k+1):
        if j > a[i-1]:
            if i is 1:
                break
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        if j > a[i-1]:
            dp[i][j] -= dp[i-1][j-1-a[i-1]]
        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 for i in range(0,K+1)] for i in range(0,N)]
for i in range(0,K+1):
    if A[0]>=i:
        dp[0][i]=1

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

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

Submission status: Accepted

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

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

# dp[i] -> number of ways to distribute i candies to n childers
MOD = 10**9 + 7
dp = [0]*(k+1)

dp[0] = 1
pref = [0] + [1]*(k+1)
for i in range(n):
    for left in range(k,0,-1):
        dp[left] += pref[left] - pref[left - min(arr[i],left)]
        dp[left] %= MOD
        # for give in range(1,min(arr[i],left)+1):
        #     dp[left] += dp[left-give]
    pref = [0]
    for e in dp:
        pref.append(pref[-1] + e)

print(dp[k]%MOD)

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

mod = 10 ** 9 + 7
dp = [0] * (k + 1)

dp[0] = 1

for i in a:
    neg = [0] * (k + 1)
    s = 0
    dp2 = [0] * (k + 1)
    
    for j in range(k + 1):
        s += dp[j]
        s %= mod
        dp2[j] = s
        neg[min(k, j + i)] += dp[j]
        s -= neg[j]
    
    dp = dp2

print(dp[-1])

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
dp_sum = [[0]*(k+1) for i in range(n+1)]
for i in range(k+1):
    dp_sum[0][i] = 1
for i in range(n):
    for j in range(k+1):
        dp[i+1][j] += dp_sum[i][j]
        if j - a[i] > 0:
            dp[i+1][j] -= dp_sum[i][j-a[i]-1]
        if j -1 >= 0:
            dp_sum[i+1][j] = dp_sum[i+1][j-1]+dp[i+1][j]
        else:
            dp_sum[i+1][j] = dp[i+1][j]
        dp[i+1][j] %= mod
        dp_sum[i+1][j] %= mod
print(dp[-1][-1]%mod)

Submission status: Accepted

Solution code:
from itertools import accumulate
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
dp = [[0 for i in range(k+1)] for j in range(n+1)]
dp[0][0] = 1
asum = 0
for i in range(1,n+1):
  acc = list(accumulate(dp[i-1]))
  ai = a[i-1]
  asum += ai
  for j in range(min(k,asum)+1):
    dp[i][j] = acc[j]
    if j > ai:
      dp[i][j] -= acc[j-ai-1]
    dp[i][j] %= mod
print(dp[n][k])

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) for i in range(N+1)]
S = [0] * (K+2)
dp[0][0] = 1
for i in range(1,N+1):
    for j in range(1,K+2):
        S[j] = (S[j-1] + dp[i-1][j-1])%mod
    for j in range(K+1):
        dp[i][j] = (S[j+1] - S[max(0, j-a[i-1])])%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) for i in range(n+1)]
# dp[i][j]: i人目まで配ったときに残っているアメの個数がj個となる場合の数
from itertools import accumulate
dp[0][k] = 1
for i in range(n):
    x = [0]*(k+2)
    for j in range(k+1):
        x[max(0, j-A[i])] += dp[i][j]%mod
        x[j+1] -= dp[i][j]%mod
    cum = list(accumulate(x))
    dp[i+1] = cum

print(dp[n][0]%mod)

Submission status: Accepted

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

# 子供iまででkを作った場合の組み合わせの数をdp[i][k]とすると、
# dp[i][k] = sum_a(in a[i]) dp[i-1][k-a] と計算できるが、
# N, Kに加えて各a_iについての3重ループになってしまうため工夫が必要（naive実装：TLE）


'''
3 4
1 2 3
'''

from itertools import accumulate

N, K = map(int, input().split())
A = [int(i) for i in input().split()]

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

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

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

    # print(i, A[i - 1])
    for k in range(1, K + 1):
        # naive実装
        # res = 0
        # for a in range(0, A[i-1] + 1):
        #     if k - a >= 0:
        #         res += dp[i-1][k-a]
        # dp[i][k] = res % DIVISOR

        dp[i][k] = dp_cum[i-1][k+1] - dp_cum[i-1][max(0, k-A[i-1])]

    dp_cum[i] = [0] + list(accumulate(dp[i]))
    dp_cum[i] = [i % DIVISOR for i in dp_cum[i]]

# print(dp)
# print(dp_cum)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod =10**9+7

#dp[i][j]:0~iまでの子がj個分け合う場合の数
dp = [[0]*(k+1) for i in range(n)]
#b[q+1]-b[p] = dp[x][p]+...+dp[x][q]
b = [0]*(k+2)

for i in range(k+1):
    if i <= a[0]:
        dp[0][i] = 1
    b[i+1] = b[i]+dp[0][i] 

for i in range(1,n):
    for j in range(k+1):
        dp[i][j] = (b[j+1]-b[max(0,j-a[i])])%mod
    #bの更新
    b[0] = 0
    for j in range(k+1):
        b[j+1] = (b[j]+dp[i][j])%mod
        dp[i][j] = dp[i][j]%mod
print(dp[-1][-1])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
a = [-1] + 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):
    for j in range(K):
        if j - a[i+1] >= 0:
            dp[i+1][j+1] = (dp[i+1][j] + dp[i][j+1] - dp[i][j - a[i+1]]) % 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:
import sys
input = sys.stdin.buffer.readline

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    MOD = 10**9+7
    
    dp = [0 for _ in range(K+2)]
    dp[0] = 1
    for num in a:
        imos = [0 for _ in range(K+2)]
        for i in range(K+2):
            imos[i] += dp[i]
            imos[min(K+1,i+num+1)] -= dp[i]
        for i in range(K+1):
            imos[i+1] += imos[i]
            imos[i+1] %= MOD
        dp = imos
        
    print(dp[K])
        
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 _ in range(n+1)]
dp[0][0] = 1

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

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

dp = [0] * (K + 1)
dp[K] = 1
for i in range(N):
  x = a[i]
  imos = [0] * (K + 2)
  for j in range(K + 1):
    if j - x >= 0:
      imos[j - x] += dp[j]
      imos[j - x] %= mod
    else:
      imos[0] += dp[j]
      imos[0] %= mod
    imos[j + 1] -= dp[j]
    imos[j + 1] %= mod
  for j in range(K + 1):
    imos[j + 1] += imos[j]
    imos[j + 1] %= mod
  for j in range(K + 1):
    dp[j] = imos[j]
print(dp[0])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N, K = MAP()
a = LIST()

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

Submission status: Accepted

Solution code:
import sys
INF = 10 ** 15
MOD = 10 ** 9 + 7
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from math import pi
from functools import lru_cache

def main():
    n,k = map(int,input().split())
    a = list(map(int,input().split()))
    dp = [[0,1] + [0] * k for _ in range(n + 1)]

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

if __name__ =='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,k=[int(j) for j in input().split()]
a=[int(j) for j in input().split()]
mod=10**9+7
import numpy as np
dp=np.zeros((n+1,k+1),dtype=np.int64)
dp[0][0]=1
for i in range(n):
    dp[i+1]=dp[i]
    dp[i+1,a[i]+1:]-=dp[i,:-(a[i]+1)]
    np.cumsum(dp[i+1],out=dp[i+1])
    dp[i+1]%=mod
print(dp[n][k])

Submission status: Accepted

Solution code:
from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]



n,k = li()
l = sorted(li())
dp = [0]*(k + 1)
helparr = [0] + [1 for i in range(k + 1)]




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

curr = 0
for j in range(k + 1):
    curr += dp[j]
    helparr[j + 1] = curr




for i in l[1:]:
    for j in range(k,-1,-1):
        leftind = max(0,j - i)
        dp[j] = (dp[j] + helparr[j] - helparr[leftind])%mod


    curr = 0
    for j in range(k + 1):
        curr += dp[j]
        helparr[j + 1] = curr



print(dp[-1])

Submission status: Accepted

Solution code:
#

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    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 i in range(N):
        temp = dp[i][0]
        k = a[i]
        for j in range(K+1):
            if j == 0:
                dp[i+1][j] = temp
                continue
            if j <= k:
                temp += dp[i][j]
                dp[i+1][j] = temp%mod
            else:
                temp += dp[i][j] - dp[i][j-k-1]
                dp[i+1][j] = temp%mod
    print(dp[N][K]%mod)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))
m = 1000000007
# dp[i][j]: i人目までに合計j個渡したときの場合の数
# i人目に配れるアメは0~A[i-1]個
# 例えばA[i-1]個をi人目に配っていたらi-1人目まではj-A[i-1]個を合計で配っている
# dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][j-A[i-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][j-1] + dp[i-1][j] - dp[i-1][j-A[i-1]-1]


dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
# i人目までに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][j - 1] + dp[i - 1][j]) % m
        # i-1人目までに渡すアメの数は0以上でなければならない
        if (j - A[i - 1] - 1) >= 0:
            dp[i][j] = (dp[i][j] + m - dp[i - 1][j - A[i - 1] - 1]) % m
            
print(dp[N][K])

Submission status: Accepted

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

# import random
# N = 100
# K = 10**5
# A = [K] * N

if sum(A) < K:
  print(0)
  exit(0)

t0 = [0] * (K+1)
t0[0] = 1

M = 10**9 + 7
for i in range(N):
    a = A[i]
    t1 = [0] * (K+1)
    st0 = [0]
    for t in t0:
        st0.append((t + st0[-1]) % M)
    for k in range(K+1):
        l = max(0, k-a)
        t1[k] = (st0[k+1] - st0[l]) % M
    t0 = t1

print(t0[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) for i in range(n+1)]
dp[0][0]=1
B=[0]*(2*k+3) #累積和list
for i in range(1,n+1):
  for j in range(k+1):
    B[j]=B[j-1]+dp[i-1][j]
  for j in range(k+1):
    dp[i][j]=(B[j]-B[j-A[i-1]-1])%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+1) for _ in range(n)]

for j in range(a[0] + 1):
    dp[0][j] = 1

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

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

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