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: Wrong Answer

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

    for i in range(n-2,-1,-1):
        z = [None] * l
        s = z[0] = 1
        c = a[i] + 1
        for j in range(1,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]


print(main())

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = np.zeros(k + 1, dtype=np.int64)
dp[0] = 1
for a in aaa:
    dp = dp.cumsum(dtype=np.int64)
    dp %= MOD
    dp[a + 1:] -= dp[:-a - 1]
    dp %= MOD
print(dp[k])

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = np.zeros(k + 1, dtype=np.int64)
dp[0] = 1
for a in aaa:
    dp = np.cumsum(dp)
    dp[a + 1:] -= dp[:-a - 1]
    dp %= MOD
print(dp[k])

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = np.zeros(k + 1, dtype=np.int64)
dp[0] = 1
for a in aaa:
    if a == 0:
        continue
    dp = np.cumsum(dp)
    dp[a + 1:] -= dp[:-a - 1]
    dp %= MOD
print(dp[k])

Submission status: Wrong Answer

Solution code:
import numpy as np

n, k = map(int, input().split())
aaa = list(map(int, input().split()))
MOD = 10 ** 9 + 7
dp = np.zeros(k + 1, dtype=int)
dp[0] = 1
for a in aaa:
    if a == 0:
        continue
    acc = np.cumsum(dp)
    dp = acc
    dp[a + 1:] -= acc[:-a - 1]
    dp %= MOD

print(dp[k] % MOD)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

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

print((dp[-1][-1]-dp[-2][-1])%1000000007)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

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

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

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(1,n+1):
    for j in range(1,k+1):
      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: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(k+1) for _ in range(n+1)]
mod=1000000007
#i人目までに0個配る方法は1通り
for i in range(n+1):
  dp[i][0]=1

def main():
  for i in range(1,n+1):
    for j in range(1,k+1):
      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]%mod)
main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(k+1) for _ in range(n+1)]
mod=10**9+7
#i人目までに0個配る方法は1通り
for i in range(n+1):
  dp[i][0]=1

def main():
  for i in range(1,n+1):
    for j in range(1,k+1):
      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]%mod)
main()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(k+1) for _ in range(n+1)]
mod=10**9+7
#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):
    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]%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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):
    for k in range(K+1):
        s = list(itertools.accumulate(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)

Submission status: Time Limit Exceeded

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]
	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)
		psums[r][0] = dp[r][0]
		for c in range(1, k + 1):
			psums[r][c] = dp[r][c] + psums[r][c-1]
	print(dp[n-1][k] % MOD)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Solution code:
from  collections import deque

def main():
    m = int(1e9 + 7)

    n, k = map(lambda x: int(x), input().split())
    limit = tuple(map(lambda x: int(x), input().split()))

    if n > 1:
        uses = deque([
            [1 for i in range(min(limit[0] + 1, k + 1))]
        ])

        for i in range(1, n - 1):
            maxAccumulated = min(
                k,
                limit[i] + len(uses[0]) - 1
            )

            uses.append([0] * (maxAccumulated + 1))

            for accumulated in range(len(uses[0])):
                for x in range(min(limit[i] + 1, k - accumulated + 1)):
                    uses[1][x + accumulated] += 1

            uses.popleft()

        waysToShare = 0

        for accumulated in range(len(uses[0])):
            candiesLeft = k - accumulated

            if candiesLeft <= limit[-1]:
                waysToShare = (waysToShare % m) + (uses[0][accumulated] % m)

        print(waysToShare % m)

    else:
        if k > limit[0]:
            print(0)
        else:
            print(1)

main()

Submission status: Time Limit Exceeded

Solution code:
m = 1000000007

def main():
    def total(x, index):
        if x < 0 or index < 0:
            return 0

        elif index == 0:
            if x <= limit[0]:
                return 1
            else:
                return 0

        elif x in calculated[index]:
            return calculated[index][x]

        else:
            totalWays = 0
            for v in range(limit[index] + 1):
                if x - v < 0: break
                totalWays += total(x - v, index - 1)

            calculated[index][x] = totalWays
            return totalWays % m

    n, k, limit = getInputs()

    calculated = []
    for i in range(n):
        calculated.append({})

    waysToShare = total(k, n - 1)
    print(waysToShare)

def getInputs():
    n, k = map(lambda x: int(x), input().split())
    limit = tuple(map(lambda x: int(x), input().split()))

    return n, k, limit

main()

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
MOD = 10**9+7
dp = [[0 for j in range(K+10)] for i in range(N+10)]
#初期化
for l in range(A[0]+1):
    dp[0][l] = 1

for i in range(1,N):
    for k in range(K+1):
        dp[i][k] = dp[i-1][k] + dp[i][k-1] - dp[i-1][max(-1, k-A[i]-1)]
        dp[i][k] %= MOD
print(dp[N-1][K])

Submission status: Time Limit Exceeded

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+10,K+10),dtype=np.int64)

for i in range(N):
    for k in range(K+1):
        if i == 0:#初期化
            dp[0,:A[0]+1] = 1
            break
        else:
            dp[i][k] = dp[i-1,k] + dp[i,k-1] - dp[i-1,max(-1, k-A[i]-1)]
        dp[i][k] %= MOD
print(dp[N-1][K])

Submission status: Time Limit Exceeded

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+10,K+10),dtype=np.int64)

for i in range(N):
    for k in range(K+1):
        if i == 0:#初期化
            dp[0,:A[0]+1] = 1
            break
        else:
            dp[i][k] = np.sum(dp[i-1, max(0,k-A[i]):k+1])
        dp[i][k] %= MOD
print(dp[N-1][K])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

    def max2(x, y): return x if x >= y else y

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

    dp = [0] * (K+1)
    dp[0] = 1
    for A in As:
        accDP = [0] + list(accumulate(dp))
        accDP = [accDPi % MOD for accDPi in accDP]
        dp = [(accDP[j+1] - accDP[max2(0, j-A)]) % MOD for j in range(K+1)]

    print(dp[K])


solve()

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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:
    accDP = [0] + list(accumulate(dp))
    accDP = [accDPi % MOD for accDPi in accDP]
    dp = [(accDP[j+1] - accDP[max(0, j-A)]) % MOD for j in range(K+1)]

print(dp[K])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
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
for i in range(N):
    for k in range(K+1):
        for j in range(arr[i]+1):
            if k-j >= 0:
                dp[i+1][k] += dp[i][k-j]
print(dp[-1][-1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

mod = 10**9 + 7

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

for i, a in enumerate(A):
    dp = list(accumulate(dp))
    for j in range(K, a, -1):
        dp[j] -= dp[j-a-1]
        dp[j] %= mod

print(dp[K] % mod)

Submission status: Time Limit Exceeded

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

MOD = pow(10, 9) + 7

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

for i in range(N):
    S = [0] * (K+1)
    S[0] = dp[i][0]
    # 累積和
    for j in range(1, K+1):
        S[j] = (dp[i][j] + S[j - 1]) % MOD

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

print(dp[N][K])

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,input().split())
li=[int(k) for k in input().split()]
tot=0
ans=0
def findans(tot,li,j,k):
    global ans
    if k-tot==0 :
        ans+=1
    
        return 1
    if k<0:
        return 0
    if j==len(li):
        return 0    
    for i in range(li[j]+1):
        
        x=findans(tot+i,li,j+1,k)
    
    
findans(0,li,0,k)
mod=10**9+7
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
def main():
    MOD = 10 ** 9 + 7
    N, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    dp = [[0 for _ in range(K + 1)] for _ in range(N + 1)]
    for n in range(N + 1):
        dp[n][0] = 1
    for n in range(1, N + 1):
        dp_left = dp[n][0]  # dp[n][k - 1]
        for k in range(1, K + 1):
            val = dp_left + dp[n - 1][k]
            kk = k - A[n - 1] - 1
            if kk >= 0:
                val -= dp[n - 1][kk]
            val %= MOD
            dp[n][k] = val
            dp_left = val
    print(dp[N][K])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
MOD=10**9+7
def solve(N:int,K:int,A:list)->int:
    #dp[i][j]:=i人目までの子供にj個の飴を配る場合の数
    dp=[[0]*(K+1) for i in range(N+1)]
    for i in range(N):dp[i][0]=1
    sum=[0]*(K+2)
    for i in range(N):
        for j in range(K+1):#累積和
            sum[j+1]=(sum[j]+dp[i][j])%MOD
        for j in range(K+1):
            dp[i+1][j]=(sum[j+1]-sum[max(0,j-A[i])]+MOD)%MOD
            dp[i+1][j]%=MOD
    return dp[N][K]
def main(lines):
    N,K=map(int,lines[0].split())
    A=list(map(int,lines[1].split()))
    print(solve(N,K,A))
if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from random import randint 
mod=10**9+7
def ways(n,k,arr):
	dp=[[0]*(k+1) for _ in range(n)]
	for i in range(arr[0]+1):
		dp[0][i]=1
	for i in range(1,n):
		s=0
		start=0
		for j in range(k+1):
			s+=dp[i-1][j]
			if s>mod:
				s-=mod
			dp[i][j]=s
			if j-start==arr[i]:
				s-=dp[i-1][start]
				if s<0:
					s+=mod
				start+=1

	return dp[n-1][k]
			

# with open ('input.txt') as f :
n,k=map(int,input().split())
arr=list(map(int,input().split()))
res=ways(n,k,arr)
# res=ways(100,10**5,[randint(0,10**5) for _ in range(100)])
print(res)

Submission status: Time Limit Exceeded

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 = [0] + list(accumulate(dp))
    for i in range(K + 1):
        dp[i] = (S[i + 1] - S[max(0, i - a)]) % mod

print(dp[K])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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)]
dp[0][0] = 1
for i, a in enumerate(A):
  for j in range(k+1):
    if j == 0:
      dp[i+1][j] = 1
    elif j <= a:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j]
    else:
      dp[i+1][j] = dp[i+1][j-1] + dp[i][j] - dp[i][j-a-1]
    dp[i+1][j] %= MOD
ans = dp[n][k]
print(ans)

Submission status: Time Limit Exceeded

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

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

print(dp[N][K])

Submission status: Time Limit Exceeded

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]

print(dp[n][k] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

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] * (n + 1) for i in range(k + 1)]

for i in range(k + 1):
    for j in range(1, n + 1):
        if i > cs_a[j - 1]:
            dp[i][j] = 0
        elif i == 0:
            dp[i][j] = 1
        elif i == 1:
            dp[i][j] = dp[i][j - 1] + min(1, a[j - 1])
        else:
            dp[i][j] = sum(dp[i - x][j - 1] for x in range(a[j - 1] + 1))

print(dp[k][n] % (10 ** 9 + 7))

Submission status: Time Limit Exceeded

Solution code:
import collections
N,K=map(int,input().split())
#N=int(input())
A=list(map(int,input().split()))
M=10**9+7
dp=[[0]*(K+2)for i in range(N+1)]
for i in range(N+1):
    dp[i][0]=1

for i in range(1,A[0]+1):
    dp[0][i]=1
for i in range(N-1):
    for j in range(K+1):
        if j-A[i+1]<0:
            dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1])%M
        else:
            dp[i+1][j+1] = (dp[i+1][j]+dp[i][j+1]-dp[i][j-A[i+1]])%M
print(dp[N-1][K])

Submission status: Time Limit Exceeded

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
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+=p[i]
		dp[i]+=su
print(dp[k]%(10**9+7))
#print(dp[0][n-1])

Submission status: Time Limit Exceeded

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)] for i in range(k + 1)]

    print(dp[k])
resolve()

Submission status: Time Limit Exceeded

Solution code:
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
mod=pow(10,9)+7
z=[[0]*(k+1) for i in xrange(n+1)]
z[0][0]=1
for i in xrange(n):
  for j in xrange(k):
	z[i][j+1]+=z[i][j]
  for j in xrange(k+1):
    z[i+1][j]=z[i][j]
    if j-a[i]-1>=0:
      z[i+1][j]-=z[i][j-a[i]-1]
print z[n][k]%mod

Submission status: Time Limit Exceeded

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
    mod = 10**9 + 7
    # dp[i][j] i人目まで配って、残りがj個の方法の数
    s = [1]*(K+2)
    s[-1] = 0
    tmp = 0
    for i in range(1, N+1):
        next = [0]*(K+2)
        for j in range(K, -1, -1):
            tmp = s[j] - s[min(K, j+a[i-1]) + 1]
            tmp %= mod
            dp[i][j] = tmp
            next[j] = (next[j+1]+tmp) % mod
        s = list(next)

    print(tmp)


main()

Submission status: Time Limit Exceeded

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個の方法の数
    s = [1]*(K+2)
    s[-1] = 0
    for i in range(1, N+1):
        tmp = 0
        next = [0]*(K+2)
        for j in range(K, -1, -1):
            tmp = s[j] - s[min(K, j+a[i-1]) + 1]
            tmp %= mod
            dp[i][j] = tmp
            next[j] = (next[j+1]+tmp) % mod
        s = list(next)

    print(dp[-1][0])


main()

Submission status: Time Limit Exceeded

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個の方法の数
    s = [0]*(K+2)
    for i in range(1, N+1):
        tmp = 0
        for j in range(K, -1, -1):
            s[j] = (s[j+1] + dp[i-1][j]) % mod
        for j in range(K, -1, -1):
            tmp = s[j] - s[min(K, j+a[i-1]) + 1]
            tmp %= mod
            dp[i][j] = tmp

    print(dp[-1][0])


main()

Submission status: Time Limit Exceeded

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

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

MOD = 1000000007  # type: int


def debug(s):
    print(s)


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):
        ai = a[i - 1]
        dp[i][0] = 1
        for k in range(1, K + 1):
            c = dp[i - 1][k] + dp[i][k - 1]
            if k - ai - 1 >= 0:
                c -= dp[i - 1][k - ai - 1]
            dp[i][k] = c % MOD
            # debug(f"{i} kids share {k} candies: => {dp[i][k]}")
    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 = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(solve(N, K, a))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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]
        if j-a[i]>0:
            dp[i+1][j]= dp_sum[i][j] - dp_sum[i][j-a[i]-1]
        else:
            dp[i+1][j]= dp_sum[i][j]

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, K = map(int, input().split())
A = tuple(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(1, N + 1):
    S = [0] + list(itertools.accumulate(dp[i - 1]))
    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: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,k,s,d):
    if i==n:
        return k==0
    if k<0 or k-s>0:
        return 0
    if (i,k) not in d:
        d[i,k]=sum(f(i+1,k-j,s-a[i],d) for j in xrange(min(k,a[i])+1))%(pow(10,9)+7)
    return d[i,k]
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
print f(0,k,sum(a),{})

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,k,s,d):
    if i==n:
        return k==0
    if k<0 or k-s>0:
        return 0
    if (i,k) not in d:
        d[i,k]=sum(f(i+1,k-j,s-a[i],d) for j in xrange(min(k,a[i])+1))%(pow(10,9)+7)
    return d[i,k]
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
print f(0,k,sum(a),{})

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
def f(i,k,s,d):
    if i==n:
        return k==0
    if k<0 or k-s>0:
        return 0
    if (i,k) not in d:
        d[i,k]=sum(f(i+1,k-j,s-j,d) for j in xrange(a[i]+1))%(pow(10,9)+7)
    return d[i,k]
n,k=map(int,raw_input().split())
a=map(int,raw_input().split())
print f(0,k,sum(a),{})

Submission status: Time Limit Exceeded

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