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:
def main():
  M=10**9+7
  n,k,*a=map(int,open(0).read().split())
  dp=[[1]+[0]*k]
  for b,i in zip(dp,a):
    t,d=0,[]
    for v in b[:i+1]:
      t+=v
      t%=M
      d+=t,
    for w,v in zip(b,b[i+1:]):
      t+=v-w
      t%=M
      d+=t,
    dp+=d,
  print(t)
main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

"""
(1+x+...+x^a) をたくさんかける
(1-x^{a+1}) をかけて、(1-x)^{-1}をかける
"""

import numpy as np
MOD = 10 ** 9 + 7
N,K = map(int,input().split())
dp = np.zeros(K+1, dtype=np.int64)
dp[0] = 1

for a in map(int,input().split()):
    # numpyのバージョン違いにより
    prev = dp.copy()
    dp[a+1:] -= prev[:-(a+1)]
    np.cumsum(dp, out=dp)
    dp %= MOD

answer = dp[K]
print(answer)

Submission status: Accepted

Solution code:
def solve():
    k, a = read()
    result = think(k, a)
    write(result)


def read():
    n, k = read_int(2)
    return k, read_int(n)


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(k, a):
    mode = 10 ** 9 + 7
    n = len(a)

    # dp[i][j], means ways to count, for from 0th to ith child, candies num is j
    # dp[i][j] = sum(dp[i - 1][j - k]), which k is 0 to a[i]
    dp = [[0 for x in range(k + 1)] for y in range(n)]
    dp[0][0] = 1

    accumulated_a = [0 for x in range(n)]
    accumulated_a[0] = a[0]
    for i in range(1, n):
        accumulated_a[i] = accumulated_a[i - 1] + a[i]

    if accumulated_a[n - 1] < k:
        return 0

    accumulated_dp = [0] * (k + 2)

    # accum[0] = 0
    # accum[1] = dp[i][0]
    # accum[2] = dp[i][0] + dp[i][1]
    # accum[k] = dp[i][0] + dp[i][1] + ... + dp[i][k - 1]
    # accum[k + 1] = dp[i][0] + dp[i][1] + ... + dp[i][k]

    for i in range(n):
        for j in range(min(accumulated_a[i] + 1, k + 1)):
            if i == 0 and j == 0:
                continue
            if i == 0:
                if j <= a[i]:
                    dp[i][j] = 1
            else:
                # add (dp[i - 1][j - a[i]] to dp[i - 1][a[i]])
                dp[i][j] += accumulated_dp[j + 1] - accumulated_dp[max(j - a[i], 0)]
                dp[i][j] %= mode

        for y in range(k + 1):
            accumulated_dp[y + 1] = accumulated_dp[y] + dp[i][y]

    return dp[n - 1][k]


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
MAX_INT = int(10e2)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,K = IL()
a = IL()

dp = [[0]*(K+1) for i in range(N+1)] # dp[i人までの子どもが][j個のアメを配る]
Cs = [[0]*(K+1) for i in range(N+1)] # 累積和

aa = a[0]
num = 0
for i in range(K+1):
  if i <= aa:
    dp[1][i] = 1
    num += 1
  Cs[1][i] = num
for i in range(2,N+1):
  num = 0
  for j in range(K+1):
    if j-a[i-1]-1 < 0:
      dp[i][j] = Cs[i-1][j] %mod
    else:
      dp[i][j] = (Cs[i-1][j] - Cs[i-1][j-a[i-1]-1]) %mod
    num += dp[i][j]
    Cs[i][j] = num

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

Submission status: Accepted

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

MOD = 10 ** 9 + 7
DP = [[0] * (K + 1) for _ in range(N)]

for i in range(a[0] + 1):
  DP[0][i] = 1

L = [0] * (K + 1)
for i in range(1, N):
  L[0] = 1
  for j in range(1, K + 1):
    L[j] = (DP[i - 1][j] + L[j - 1]) % MOD
  x = a[i]
  for j in range(K + 1):
    if j <= x:
      DP[i][j] = L[j]
    else:
      DP[i][j] = L[j] - L[j - x - 1]
      while DP[i][j] < MOD:
        DP[i][j] += MOD

print(DP[N - 1][K] % MOD)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
from functools import reduce
import sys
import math
import bisect
import random 

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return list(map(float, sys.stdin.readline().split()))
def LS():return sys.stdin.readline().split()
def SR(n): return [list(sys.stdin.readline())[:-1] for i in range(n)]
def IR(n): return [int(sys.stdin.readline()) for i in range(n)]
def LIR(n): return [list(map(int, sys.stdin.readline().split())) for i in range(n)]
def LSR(n): return [list(map(list, sys.stdin.readline().split())) for i in range(n)]
_gcd = lambda x, y: _gcd(y, x%y) if (x%y) else y
_lcm = lambda x, y: x*y // _gcd(x, y)
def gcd(*numbers):
    return reduce(_gcd, numbers)
def lcm(*numbers):
    return reduce(_lcm, numbers)
sys.setrecursionlimit(1000000)
INF = float('inf')
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, K = LI()
a = LI()
"""

dp = np.zeros(K+1, dtype=np.int64)
dp[0:a[0]+1] = 1

for i in range(1,N):
    acc = np.cumsum(dp)
    for j in range(K+1)[::-1]:
        if (j-a[i]<=0):
            dp[j] = acc[j]%mod
        else:
            dp[j] = (acc[j] - acc[j-a[i]-1])%mod

print(dp[K])

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

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

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

    acc[0] = 0
    for j in range(K+1):
        acc[j+1] = (acc[j] + dp[j])%mod

print(dp[K])

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

# N < 100 , K < 10^5
N,K = inpl()
aa = inpl()

dp = [[0]*(K+1) for _ in range(N)]
# dp[i][k] : i人目までに k個を配る場合の数
# dp[i][k] = sum(a=0,aa[i]) dp[i-1][k-a]
#          = sum(x=k-aa[i],k) dp[i-1][x]


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

for i in range(1,N):
    tmp = 0
    rdp = [0]*(K+2)
    for k in range(K+1):
        tmp += dp[i-1][k]
        tmp %= mod
        rdp[k+1] = tmp

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

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

Submission status: Accepted

Solution code:
##x_1+x_2+...+x_N=K, 0<=x_i<=a_i
N,K=list(map(int,input().strip().split(' ')))
A=list(map(int,input().strip().split(' ')))
dp=[[0] * (K+1)  for i in range(N)]
for i in range(min(A[0]+1,K+1)):
    dp[0][i]=1
for i in range(N):
    dp[i][0]=1
MOD=10**9+7
for i in range(1,N):
    pre=[]
    temp=0
    for j in range(K+1):
        temp+=dp[i-1][j]
        temp%=MOD
        pre+=[temp]
        
    for j in range(1,K+1):
        ## j-A[i],j-(A[i]-1),...,j
        ## pre[j]-pre[j-A[i]-1]
        temp=0
        if j-A[i]>0:
            temp=pre[j-A[i]-1]
        dp[i][j]=pre[j]-temp
        dp[i][j]%=MOD

print(dp[-1][K])

Submission status: Accepted

Solution code:
# @author 

import sys

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

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

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

        # d = 0
        # dp[k][i] Number of ways of getting k with the first i constraints
        pre = [[0] * (n + 1) for _ in range(k + 2)]
        for i in range(n + 1):
            pre[0][i] = 1
        for v in range(1, k + 1):
            pre[v][0] = pre[v - 1][0]
            for i in range(1, n + 1):
                dp[v][i] += (pre[v][i - 1] - pre[v - min(v, a[i - 1]) - 1][i - 1]) % MOD
                pre[v][i] = pre[v - 1][i] + dp[v][i]

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

solver = MCandies()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
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[n][k]...n人目まででk個の飴を分ける組み合わせ
dp[0][0] = 1
	
for n in range(1, N + 1):
	#cum...累積和
	cum = [0] * (K + 2)
	for k in range(K + 1):
		cum[k + 1] = cum[k] + dp[n - 1][k]
		dp[n][k] = cum[k + 1] - cum[max(0, k - a[n - 1])]
		dp[n][k] %= mod

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

Submission status: Accepted

Solution code:
import fileinput


def solve_candies(ch_count, total_canides, capacity_list):
    mod = 10**9 + 7
    last_solutions = [0] * (total_canides + 1)
    last_solutions[0] = 1

    all_total = 0
    for current_child in range(ch_count):
        current_cap = capacity_list[current_child]

        new_total = min(all_total + current_cap, total_canides)

        current_solutions = [0] * (total_canides + 1)

        current_sum = 0
        summed_candies = 0

        for total in range(new_total + 1):
            current_sum += last_solutions[total]
            summed_candies += 1
            if summed_candies > current_cap + 1:
                current_sum -= last_solutions[total - current_cap - 1]

            current_solutions[total] = current_sum % mod

        last_solutions = current_solutions
        all_total = new_total

    return last_solutions[-1]


inp = fileinput.FileInput()

split = inp.readline().split(" ")
children = int(split[0])
total_candies = int(split[1])
caps = [int(v) for v in inp.readline().split()]

print(solve_candies(children, total_candies, caps))

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 a in A:
    dp2 = [0]*(K+1)
    for i in range(K+1):
        dp2[i] += dp[i]
        if i + a + 1 <= K:
            dp2[i+a+1] -= dp[i]
    for i in range(1, K+1):
        dp2[i] = (dp2[i-1] + dp2[i]) % mod
    dp = dp2[:]
print(dp[-1])

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
MOD=10**9+7

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

dp=[0]*(2*k+1)
dp[0]=1
for a in aa:
    l=k-a
    s=sum(dp[l:k+1])%MOD
    for i in range(k,-1,-1):
#        print(s,i,l)
        s-=dp[i]
        s%=MOD
        dp[i] += s
        l-=1
        s+=dp[l]
#    print(dp)
        
    
print(dp[k]%MOD)

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

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

for i in range(2, 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]:
            dp[i][j] -= (dp[i - 1][j - a[i - 1] - 1]) % mod
        dp[i][j] %= mod
print(dp[n][k])

Submission status: Accepted

Solution code:
import numpy as np


def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = np.zeros(k + 1, dtype=np.int64)
    dp[0] = 1
    for a in a_s[:-1]:
        dp = np.cumsum(dp) % md
        if k != a:
            dp[k:a:-1] = (dp[k:a:-1] - dp[k - a - 1::-1]) % md
    return np.sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))

Submission status: Accepted

Solution code:
def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

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

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

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

Submission status: Accepted

Solution code:
# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))

Submission status: Accepted

Solution code:
mod=10**9+7
n,k=map(int,input().split())
A=tuple(map(int,input().split()))
DP=[[0]*(k+1) for _ in range(n)]
acc=[0]*(k+2)
for i in range(k+1):
    if i<=A[0]:
        DP[0][i]=1
    acc[i+1]=acc[i]+DP[0][i]
for i in range(1,n):
    for j in range(k+1):
        DP[i][j]=(acc[j+1]-acc[max(0,j-A[i])])%mod
    acc[0]=0
    for j in range(k+1):
        acc[j+1]=(acc[j]+DP[i][j])%mod
print(DP[-1][-1])

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 = list(map(int,input().split(" ")))

mod = 10 ** 9 + 7

dp = [ [0]*(K+1) for _ in range(N) ]
acc = [ [0]*(K+1) for _ in range(N) ]
mn = min(K,a[0])

for i in range(K+1):
    if i <= mn:
        dp[0][i] = 1
    acc[0][i] = (acc[0][i-1] + dp[0][i])%mod if i > 0 else dp[0][i]%mod

for i in range(1,N):
    dp[i][0] = dp[i-1][0]
    acc[i][0] = dp[i][0]
    for k in range(1,K+1):
        if k - a[i] <= 0:
            dp[i][k] = acc[i-1][k]  % mod 
        else:
            dp[i][k] = (acc[i-1][k] - acc[i-1][k-a[i]-1]) % mod
        acc[i][k] = (acc[i][k-1] + dp[i][k])%mod

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

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 1000000007
## dp[i][j] i番目までの子供にj個の飴を分け与える通り数の""jについての累積和""

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

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

print((dp[n-1][k+1]-dp[n-1][k])%mod)

## 累積和を使わない

#dp = [[0]*(k+1) for i in range(n)]
#
#for j in range(k+1):
#  if j <= a[0] : 
#    dp[0][j] = 1
#  else:
#    dp[0][j] = 0
#for i in range(1,n):
#  for j in range(k+1):
#    for jj in range(max(0,j-a[i]),j+1): 
#      dp[i][j] += dp[i-1][jj]
#print(dp[n-1][k]%1000000007)

Submission status: Accepted

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

N,K=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())


mod=10**9+7

T=[1]
for a in A:
	W=[0]		#WA:累積和
	l=len(T)
	for j,x in enumerate(T):
		if j==0:	W.append( x%mod )
		else:	W.append( (W[-1]+x)%mod )

	T=[]  #Temporary
	for k in range( min (K+1,a+l) ):
		#print k, min( k+1, l), max(0,k-a), W[min( k+1, l)]-W[max(0,k-a)]
		T.append( W[min( k+1, l)]-W[max(0,k-a)] )


try:
	print T[K]%mod
except IndexError:
	print 0

Submission status: Accepted

Solution code:
n, k = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
p = 10 ** 9 + 7

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):
        DP[i+1][j+1] = DP[i + 1][j]
        DP[i+1][j+1] += DP[i][j+1]
        if j - A[i] >= 0: DP[i+1][j+1] -= DP[i][j - A[i]]
        DP[i+1][j+1] %= p
    
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[i][k]: i人目まで見たときにk個アメを配った場合の数
dp = [[0] * (k+1) for _ in range(n+1)]

# 始点は1、それ以外は0で初期化
dp[0][0] = 1

for i in range(1, n+1):
    # dp[i-1]の累積和をループを回しながら計算する
    # 累積和は0を含んだ0-basedの半開区間でかく (1-indexed)
    cum = [0] * (k+2)
    for j in range(k+1):
        cum[j+1] = (cum[j] + dp[i-1][j]) % mod
        dp[i][j] += cum[j+1] - cum[max(0, j-a[i-1])]
        dp[i][j] %= mod

print(dp[n][k])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
A = [int(a) for a in input().split()]
P = 10**9+7
def cumsum(A):
    B = [A[0]]
    for i in range(1, len(A)):
        B.append((B[-1]+A[i])%P)
    return B

dp = [1] + [0] * (K+N)
for a in A:
    dp = [(dp[i]-(dp[i-a-1] if i>=a+1 else 0))%P for i in range(K+1)]
    dp = cumsum(dp)
print(dp[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 = [[0] * (K+1) for _ in range(N+1)]
    dp[0][K] = 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

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

mod = 10 ** 9 + 7

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

for i in range(N):
    acc_dp = [0] + list(accumulate(dp))

    cand_dp = [0] * (K + 1)
    for k in range(K + 1):
        cand_dp[k] = acc_dp[k + 1] - acc_dp[max(0, k - a_list[i])]
        cand_dp[k] %= mod
    dp = cand_dp
print(dp[K])

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline

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

p = list(accumulate(a))

dp = [0] * (K+1)
dp[0] = 1
prefix = [0]+[1]*(K+1)
for i in range(N):
    new_dp = [0]*(K+1)
    for j in range(min(p[i],K)+1):
        new_dp[j] = prefix[j+1] - prefix[max(0,j-a[i])]
    dp = new_dp[:]
    prefix = [i % MOD for i in [0]+list(accumulate(dp))]

print(dp[K]%MOD)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline

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

p = list(accumulate(a))

dp = [0] * (K+1)
dp[0] = 1
prefix = [0]+[1]*(K+1)
for i in range(N):
    new_dp = [0]*(K+1)
    for j in range(min(p[i],K)+1):
        new_dp[j] = prefix[j+1] - prefix[max(0,j-a[i])]
    dp = new_dp[:]
    prefix = [i % MOD for i in [0]+list(accumulate(dp))]

print(dp[K]%MOD)

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

MOD = int(1e9+7)

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

for n in range(N):

    sumlist = [0]
    sumlist += dp[:]
    sumlist = list(accumulate(sumlist))

    ndp = [0] * (K+1)
    for k in range(K+1):
        ndp[k] = sumlist[k+1] - sumlist[max(0, k - A[n])] 
        ndp[k] %= MOD
    dp = ndp
                # dp[k] ~ dp[k-A[n]] made
print(dp[K]%MOD)

Submission status: Accepted

Solution code:


MOD = 1000000007

n, k = map(int, raw_input().split())
a = map(int, raw_input().split())

dp = [[0] * (k + 1) for _ in range(n + 1)]
dp[0][0] = 1
for i in range(1, n + 1):
    suma = 0
    l = 0
    r = 0
    for j in range(k + 1):
        if l < j - a[i - 1]:
            suma -= dp[i - 1][l]
            l += 1
        if r <= j:
            suma += dp[i - 1][r]
            r += 1
        suma %= MOD
        dp[i][j] += suma
        dp[i][j] %= MOD
print(dp[n][k])

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,k = LI()
    a = LI()
    l = k + 1

    y = [1] * (a[-1]+1) + [0] * (l-a[-1]-1)

    for i in range(n-2,-1,-1):
        z = [None] * l
        s = 0
        c = a[i] + 1
        for j in range(c):
            z[j] = s = (s + y[j]) % mod

        for j in range(c,l):
            z[j] = s = (s + y[j] - y[j-c]) % mod

        y = z

    return (y[-1] + mod) % mod


print(main())

Submission status: Accepted

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

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

for a in A:
  t,dp[K] = dp[K], sum(dp[j] for j in range(K-a,K+1)) % MOD

  for i in reversed(range(K)):
    t,dp[i] = dp[i], (dp[i+1]-t+(dp[i-a] if i >= a else 0)) % MOD

print(dp[K])

Submission status: Accepted

Solution code:
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0]*(K+1)
dp[0] = 1
MOD = 10**9 + 7
for i in range(N):
    c = sum(dp[K-A[i]:K+1]) % MOD
    for j in range(K, -1, -1):
        v = dp[j]
        dp[j] = c
        c -= v
        if j-A[i]-1 >= 0:
            c += dp[j-A[i]-1]
        c %= MOD
print(dp[K])

Submission status: Accepted

Solution code:
from itertools import accumulate

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
MOD = 10**9+7

for i,a in enumerate(A):
    ac = [0] + list(accumulate(dp[i]))
    for j in range(K+1):
        dp[i+1][j] = (ac[j+1] - ac[max(0,j-a)]) % MOD
print(dp[-1][-1])

Submission status: Accepted

Solution code:
from itertools import accumulate, starmap
from operator import sub

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = [0] * (k + 1)
dp[0] = 1
for a in aaa:
    dp = list(accumulate(dp))
    dp[a + 1:] = starmap(sub, zip(dp[a + 1:], dp[:-a - 1]))
    dp = [x % MOD for x in dp]
print(dp[k])

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
A=[int(i) for i in input().split()]
dp=[[0]*(K+1) for i in range(N+1)]
sumi=[[0]*(K+2) for i in range(N+1)]
mod=10**9+7
dp[0][K]=1
sumi[0][K+1]=1
sumi
for i in range(1,N+1):
    for k in range(K+1):
        #print(i,k)
        dp[i][k]=sumi[i-1][min(k+A[i-1],K)+1]-sumi[i-1][k]
        dp[i][k]%=mod
        sumi[i][k+1]=sumi[i][k]+dp[i][k]
        sumi[i][k+1]%=mod
print(dp[N][0]%mod)
#print(dp)

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

Submission status: Accepted

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
MOD = 10**9+7
dp = [[0 for _ in [0]*(k+1)] for _ in [0]*n]
sum_list = [[0] for _ in [0]*n]

def make_sum(i):
	for j in range(k+1):
		sum_list[i].append((sum_list[i][-1] + dp[i][j]) % MOD)
	return

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from itertools import accumulate

n,k = li()
a = list(li())
MOD = 10**9+7

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

if n > 1:   
    dp[1] = list(accumulate(dp[1]))
        
for i in range(1,n+1):
    dp[i][0] = 1
    
for i in range(2,n+1):
    for m in range(1,k+1):
        if m-a[i-1] > 0:
            dp[i][m] = dp[i-1][m] - dp[i-1][m-a[i-1]-1]
        else:
            dp[i][m] = dp[i-1][m]
        dp[i][m] %= MOD
    
    if i < n:
        dp[i] = list(accumulate(dp[i]))
        
print(dp[n][k])

Submission status: Runtime Error

Solution code:
import sys
from itertools import accumulate

def main():
  input=sys.stdin.readline
  n,k=map(int,input().split())
  A=list(map(int,input().split()))
  
  dp=[0]*(k+1)
  dp[0]=1
  for a in A:
    dp=list(accumulate(dp))
    print("accumulated",dp)
    for j,d in enumerate(dp[:k-a],start=a+1):
      dp[j]-=d
    dp=[dpi for dpi in dp]
    print(dp)
"""
def main():
  dp=[[0]*(k+1) for _ in range(n+1)]
  mod=1000000007
  #i人目までに0個配る方法は1通り
  #for i in range(n+1):
  #  dp[i][0]=1
  for i in range(0,n+1):
    for j in range(0,k+1):
      if i==0 and j==0:
        dp[i][j]=1
        break
      if j==0:
        dp[i][j]=1
        continue
      tmp=dp[i - 1][j] + dp[i][j - 1]
      if tmp>=mod:
        tmp%=mod
      dp[i][j]=tmp
      if j-a[i-1]-1>=0:
        tmp=dp[i][j]-dp[i-1][j-a[i-1]-1]
        if tmp>=mod:
          tmp%=mod
        dp[i][j]=tmp
    #print(dp)   
  print(dp[n][k])"""
main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

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

max_candies = np.array(list(map(int, input().split())))

dpt = np.full((N+1, K+1), 0, dtype='int64')
for i in range(K+1):
    dpt[0][i] = 1

@njit('i8(i8,i8,i8[:],i8[:,:]', cache=True)
def dp(N, K, max_candies, dpt):
    for i in range(1, N+1):
        for j in range(0, K+1):
            dpt[i][j] += dpt[i-1][j]
            t = j - max_candies[i-1] - 1
            if t >= 0:
                dpt[i][j] -= dpt[i-1][t]
            if j > 0:
                dpt[i][j] += dpt[i][j-1]
            dpt[i][j] = dpt[i][j] % (10**9+7)
    return (dpt[N][K] - dpt[N][K-1]) % (10**9+7)

if K > 0:
    print(dp(N, K, max_candies, dpt))
else:
    print(1)

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

N,K=map(int,input().split())
a=np.array([int(i) for i in input().split()],dtype=np.int64)

dp=np.full((N+1,K+1),0,dtype=np.int64)
c=np.full(K+2,0,dtype=np.int64)
MOD=10**9+7

@njit('i8(i8,i8,i8,i8[:,:],i8[:])', cache=True)
def main(N,K,MOD,dp,c):

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

    return dp[N][K]

print(main(N,K,dp,c))

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import njit

@njit( cache=True)
def main():
    N,K=map(int,input().split())
    a=np.array([int(i) for i in input().split()],dtype=np.int64)
    MOD=10**9+7

    dp=np.full((N+1,K+1),0,dtype=np.int64)
    c=np.full(K+2,0,dtype=np.int64)

    dp[0][0]=1


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

    print(dp[N][K])

def main()

Submission status: Runtime Error

Solution code:
N,K=map(int,input().split())
a=np.array([int(i) for i in input().split()],dtype=np.int64)
MOD=10**9+7

dp=np.full((N+1,K+1),0,dtype=np.int64)
c=np.full(K+2,0,dtype=np.int64)

dp[0][0]=1


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

print(dp[N][K])

Submission status: Runtime Error

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)
import numpy as np

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):
    for k in range(K+1):
        s = np.cumsum(dp[i-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)