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

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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def solve2(ls, k):
	dp = [0 for i in range(k + 1)]
	dp[0] = 1
	for child in ls:
		fake = [0 for i in range(k + 2)]
		for used in range(k, -1, -1):
			left = 1 + used
			left_till = min(k - used, child) + used
			if left <= left_till:
				fake[left] += dp[used]
				fake[left_till + 1] -= dp[used]
		sm = 0
		for i in range(k + 1):
			sm += fake[i]
			dp[i] += sm

	return dp[k] % 1000000007


n, k = map(int, input().split())
ls = list(map(int, input().split()))
print(solve2(ls, k))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9+7
DP = [[None for j in range(k+1)] for i in range(n+1)]
for i in range(n+1):
    DP[i][0] = 1
for j in range(1, k+1):
    DP[0][j] = 0
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]) % p
        if j > A[i-1]:
            DP[i][j] = (DP[i][j]-DP[i-1][j-1-A[i-1]]) % p
print(DP[n][k])

Submission status: Time Limit Exceeded

Solution code:
import sys
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**5+10)
# input処理を高速化する
input = lambda: sys.stdin.readline().rstrip()

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

#dp[i][j]はi人に配り終えてj個残っている状態からの場合の数
dp = [[0 for _ in range(K+1)] for _ in range(N+1)]
dp[N][0] = 1
cum = [[0 for _ in range(K+1)] for _ in range(N+1)]
cum[N] = [1] * (K+1)
for i in range(N-1, -1, -1):
    for j in range(K+1):
        if j > a[i]:
            dp[i][j] = cum[i + 1][j] - cum[i + 1][j - a[i] - 1]
        else:
            dp[i][j] = cum[i+1][j]

        if j == 0:
            cum[i][j] = dp[i][j]
        else:
            cum[i][j] = cum[i][j-1] + dp[i][j]

print(dp[0][K] % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# dp[i][j]=(i人目までにj個配る場合の数)
mod=10**9+7
def main():
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    dp=[[0]*(k+1) for _ in range(n)]
    for i in range(a[0]+1):
        dp[0][i]=1
    for i in range(1,n):
        dp[i][0]=dp[i-1][0]
        for j in range(1,k+1):
            dp[i][j]=dp[i-1][j]+dp[i][j-1]
            if j-a[i]>0:
                dp[i][j]-=dp[i-1][j-a[i]-1]
            dp[i][j]%=mod
    print(dp[-1][-1])
    # for i in dp:
    #     print(i) 
main()

Submission status: Time Limit Exceeded

Solution code:
# n=int(input())
n,k=list(map(int,input().split(" ")))
a=list(map(int,input().split(" ")))
a.sort()
m=(10**9)+7
mat=[[(1,1) for i in range(k+1)] for j in range(n+1)]
for j in range(1,k+1):
	for i in range(1,n+1):
		# i=i1-1
		if(j==1):
			if(i==1 and a[0]>0):
				x=1
				
			elif(i>0 and a[i-1]>0 ):
				x=mat[i-1][j][0]+1
				
			elif(i>0 and a[i-1]==0):
				x=mat[i-1][j][0]
				
		else:
			start=j-a[i-1]
			start=max(start,0)
			if(start==0):
				x=mat[i-1][j][1]
				
			else:
				x=mat[i-1][j][1]-mat[i-1][start-1][1]
		mat[i][j]=(x%m,(mat[i][j-1][1]+x)%m)
		# mat[i][j]=mat[i][j]%m
# print(mat)			

print(mat[n][k][0])

Submission status: Time Limit Exceeded

Solution code:
def main():
    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)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,K = map(int,input().split())
a = [0]*110
a[1:] = list(map(int,input().split()))
MOD = 10**9+7
dp = [[0]*110000 for _ in range(110)]
dp_sum = [[0]*110000 for _ in range(110)]
dp[0][0] = 1
for i in range(K+1):
    dp_sum[0][i] = 1

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

        if j-1 >= 0:
            dp_sum[i][j] = dp_sum[i][j-1] + dp[i][j]
        else:
            dp_sum[i][j] = dp[i][j]
        dp[i][j] %= MOD
        dp_sum[i][j] %= MOD
print(dp[N][K])
# for i in range(N+1):
#     print(dp[i])

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(K+1) for i 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][j-1]+dp[i-1][j]
      if j>=a[i]+1:
        dp[i][j]-=dp[i-1][j-1-a[i]]
      dp[i][j]=dp[i][j]%(10**9+7)
      
print(dp[-1][-1])

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] * (K + 1)
dp[0] = 1

for i, a in enumerate(A, start=1):
    accDp = [0] * (K + 2)
    for k in range(1, K + 2):
        accDp[k] = accDp[k - 1] + dp[k - 1]

    for k in range(K + 1):
        dp[k] = (dp[k] + accDp[k] - accDp[max(0, k - a)]) % 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 = 10**9 + 7

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

for i, a in enumerate(A, start=1):
    accDp = [0] * (K + 2)
    for k in range(1, K + 2):
        accDp[k] = accDp[k - 1] + dp[k - 1]

    for k in range(K + 1):
        dp[k] += accDp[k] - accDp[max(0, k - a)]

print(dp[K] % MOD)

Submission status: Time Limit Exceeded

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
            else:
                temp += dp[i][j] - dp[i][j-k-1]
                dp[i+1][j] = temp
    print(dp[N][K]%mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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)


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


from operator import add

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

M = 10**9 + 7
for i in range(N):
    a = A[i]
    t1 = [0] * (K+1)
    st = SegmentTree(t0, add, 0)
    for k in range(K+1):
        t1[k] = st.query(max(0, k-a), k+1) % M
    t0 = t1

print(t0[K])

Submission status: Time Limit Exceeded

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

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

#import random
#N = 3000
#A = [random.randint(1, 10**9) for _ in range(N)]
dp = [[0] * (K+1) for _ in range(N+1)]
dp[-1][0] = 1
M = 10**9 + 7
for i in range(N):
  a = A[i]
  for j in range(a+1):
    for k in range(K-j+1):
      dp[i][k+j] += dp[i-1][k]
      dp[i][k+j] %= M

#for r in dp:
#  print(r)
print(dp[N-1][K])

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e+9) + 7
LL = [0 for _ in range(K + N + 1)]
LL[0] = 1
P = [0]
for i in range(N):
  L = [[_, LL[_]] for _ in P]
  for j in L:
    if j[0] + A[i] + 1 <= K + N: #or j[0] + A[i] + 1 > K + N:
      LL[j[0]+A[i]+1] -= j[1]
      if j[0] + A[i] + 1 not in P:
        P.append(j[0]+A[i]+1)
def inved(x):
  p = mod - 2
  y = 1
  base = x
  while p != 0:
    if p % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    p //= 2
  return y
fact = [1 for i in range(K + N)]
invf = [1 for i in range(K + N)]
for i in range(K + N - 1):
  fact[i+1] = (fact[i] * (i + 1)) % mod
invf[-1] = inved(fact[-1])
for i in range(K + N - 1, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
P = 0
for i in range(K+1):
  P += (LL[i] * fact[K-i+N-1] * invf[K-i]) % mod
  P %= mod
print((P*invf[N-1])%mod)

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            s %= mod
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            self.tree[i] %= mod
            i += i & -i

    def show(self, i):
        return self.sum(i) - self.sum(i-1)


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

# xこの飴をy人に分ける
dp = [Bit(k+1) for _ in range(n+2)]
for i, a in enumerate(A):
    if i == 0:
        for j in range(a+1):
            dp[i].add(j+1, 1)
        continue
    for j in range(a+1):
        dp[i].add(j + 1, (dp[i - 1].sum(j + 1)) % mod)
    for j in range(a+1, k+1):
        dp[i].add(j + 1, (dp[i - 1].sum(j + 1) - dp[i - 1].sum(j - a)) % mod)

print(dp[n-1].show(k+1))

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            s %= mod
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            self.tree[i] %= mod
            i += i & -i

    def show(self, i):
        return self.sum(i) - self.sum(i-1)


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

# xこの飴をy人に分ける
dp = [Bit(k+1) for _ in range(n+2)]
for i, a in enumerate(A):
    if i == 0:
        for j in range(a+1):
            dp[i].add(j+1, 1)
        continue
    for j in range(k+1):
        if j <= a:
            r = j+1
        else:
            r = a+1
        dp[i].add(j+1, (dp[i-1].sum(j+1) - dp[i-1].sum(j+1-r)) % mod)

print(dp[n-1].show(k+1))

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            s %= mod
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            self.tree[i] %= mod
            i += i & -i

    def show(self, i):
        return self.sum(i) - self.sum(i-1)


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

# xこの飴をy人に分ける
dp = [Bit(k+1) for _ in range(n+2)]
for i, a in enumerate(A):
    if i == 0:
        for j in range(a+1):
            dp[i].add(j+1, 1)
        continue
    for j in range(k+1):
        r = min(j+1, a+1)
        dp[i].add(j+1, (dp[i-1].sum(j+1) - dp[i-1].sum(j+1-r)) % mod)

print(dp[n-1].show(k+1))

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
#dp[i][j] := i人目まで決め、キャンディをj個つかっているときの場合の数
dp = [[0 for i in range(k+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(k+1):
        if dp[i][j] == 0:
            break
        for candy in range(a[i]+1):
            if j + candy < k+1:
                dp[i+1][j+candy] += dp[i][j]
                dp[i+1][j+candy] %= mod
print(dp[n][k])

Submission status: Time Limit Exceeded

Solution code:
n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7
#dp[i][j] := i人目まで決め、キャンディをj個つかっているときの場合の数
dp = [[0 for i in range(k+1)] for j in range(n+1)]
dp[0][0] = 1
for i in range(n):
    for j in range(k+1):
        #index out of range
        if dp[i][j] == 0:
            continue
        for candy in range(a[i]+1):
            if j + candy < k+1:
                dp[i+1][j+candy] += dp[i][j]
                dp[i+1][j+candy] %= mod
print(dp[n][k])

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = int(1e+9) + 7
D = {0: 1}
for i in range(N):
  L = [[_, D[_]] for _ in D]
  for j in L:
    if j[0] + A[i] + 1 <= K + N: #or j[0] + A[i] + 1 > K + N:
      if j[0] + A[i] + 1 in D:
        D[j[0]+A[i]+1] -= j[1]
      else:
        D[j[0]+A[i]+1] = -j[1]
def inved(x):
  p = mod - 2
  y = 1
  base = x
  while p != 0:
    if p % 2 == 1:
      y *= base
      y %= mod
    base *= base
    base %= mod
    p //= 2
  return y
fact = [1 for i in range(K + N)]
invf = [1 for i in range(K + N)]
for i in range(K + N - 1):
  fact[i+1] = (fact[i] * (i + 1)) % mod
invf[-1] = inved(fact[-1])
for i in range(K + N - 1, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
P = 0
for i in D:
  if i <= K:
    P += (D[i] * fact[K-i+N-1] * invf[K-i]) % mod
    P %= mod
print((P*invf[N-1])%mod)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

MOD = 10**9 + 7
N, K = map(int, input().split())
*A, = map(int, input().split())
dp = [0] * (K+1)
dp[K] = 1
for a in A:
    temp = [0] * (K+1)
    for k in range(K+1):
        temp[k - min(a, k)] += dp[k]; temp[k - min(a, k)] %= MOD
        temp[k] -= dp[k]; temp[k] %= MOD
    temp = list(accumulate(temp))
    dp = [(d + t) % MOD for d, t in zip(dp, temp)]
print(dp[0] % MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def get_answer(candies,personal):
  dp = [[-1 for _ in range(candies+1)] for _ in range(len(personal) + 1)]
  def candy(rem,i,n):
    if rem<0:
      return 0
    if dp[i][rem]!= -1:  #toggle flag
      #print(rem,i)
      return dp[i][rem];
    if rem==0:
      return 1
    if i>=n:
      return 0
    ans = 0;
    for curr in range(0,personal[i] + 1):  #if i==n-1, then use up all rem?prolly
      ans+= candy(rem-curr,i+1,n)
    dp[i][rem] = ans;
    return ans
  return candy(candies,0,len(personal))

n,candies = tuple(map(int,input().split()))
personal = list(map(int,input().split()))
print(get_answer(candies,personal))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
def get_answer(candies,personal):
  dp = defaultdict(lambda : -1) 
  def candy(rem,i,n):
    if dp[str(rem) + " " + str(i)] != -1:
      #print(rem,i)
      return dp[str(rem) + " " + str(i)]
    if rem<0:
      return 0
    if rem==0:
      return 1
    if i>=n:
      return 0
    ans = 0;
    for curr in range(0,personal[i] + 1):  #if i==n-1, then use up all rem?prolly
      ans+= candy(rem-curr,i+1,n)
    dp[str(rem) + " " + str(i)] = ans;
    return ans
  return candy(candies,0,len(personal))

n,candies = tuple(map(int,input().split()))
personal = list(map(int,input().split()))
print(get_answer(candies,personal))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7

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

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

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

Submission status: Time Limit Exceeded

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

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

show_flg=False
show_flg=True

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

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

m=0
for i in range(n):
    m+=a[i]
    for x in range(k+1):
        for y in range(a[i]+1):        
            dp[i+1][x]+=dp[i][x-y]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
MOD = 1000000007

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

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

print(dp[N][K])

Submission status: Time Limit Exceeded

Solution code:
class BIT(object):
    def __init__(self, N, init=0, mod=1):
        self.N = N
        self.bit = [init for _ in range(N)]
        self.mod = mod

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w % self.mod
            self.bit[x] %= self.mod
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            s %= self.mod
            x = (x & (x + 1)) - 1
        return s

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

bit = BIT(k + 1, mod=MOD)
bit.add(0, 1)

for ai in a:
    for i in range(k, 0, -1):
        if ai >= i:
            x = bit.sum(i)
        else:
            x = bit.sum(i) - bit.sum(i - ai)
        bit.add(i, x % MOD)
print(bit.sum(k + 1) - bit.sum(k))

Submission status: Time Limit Exceeded

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


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

for a in A:
    Acum += a
    newDP = [0]*(K+1)
    for i in range(min(Acum, K) + 1):
        if i == 0:
            newDP[i] = 1
            continue
        dp[i] += dp[i - 1]
        newDP[i] = dp[i]
        if i > a:
            newDP[i] -= dp[i - a - 1]
        newDP[i] %= mod
    dp = newDP[::]

ans = dp[K]
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Jan 30 16:06:12 2020

@author: matsui
"""

import numpy as np



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

dp=np.zeros([N+1,K+1])
s=np.zeros(K+1)

for i in range(a[0]+1):
    dp[1][i]=1
          
M=a[0]
for j in range(2,N+1):
    M+=a[j-1]
    dp[j][0]=1
    
    s[0]=dp[j-1][0]
    for i in range(1,min(K+1,M+1)):
        s[i]=s[i-1]+dp[j-1][i]
      
    for i in range(1,min(K+1,M+1)):
        dp[j][i]=s[i]
        if i>a[j-1]:
            dp[j][i]-=s[i-a[j-1]-1]

        if dp[j][i] > 1e9+7: dp[j][i]=dp[j][i]%(1e9+7)
            
            
print(int(dp[N][K]))

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

# dp[i][j] i人目までの子供にj個のアメを配る数
dp = [[0] * (ｋ + 1) for _ in range(n + 1)]

for i in range(n + 1):
  dp[i][0] = 1
  
for i in range(1, n + 1):
  for j in range(1, k + 1):
    if j-1-A[i-1] >= 0:
      dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1-A[i-1]]) % MOD
    else:
      dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 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 = 10**9 + 7

dp = [[0]*(K+1) for i in range(N)]
for i, a in enumerate(A):
  if i == 0:
    for j in range(a+1):
      dp[0][j] = 1
  
  else:
    dp[i][0] = 1
    for j in range(1, K+1):
      dp[i][j] = dp[i][j-1] + dp[i-1][j]
      if j > a:
        dp[i][j] -= dp[i-1][j-a-1]

      dp[i][j] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)

N, K = map(int, raw_input().split())
A = list(map(int, raw_input().split()))
possible_ways = {}

def get_possible_ways(i, k):
    if i >= N or k < 0:
        return 0
    if k == 0:
        return 1
    if i == N-1 and k <= A[i]:
        return 1

    if (i, k) in possible_ways:
        return possible_ways[i, k]

    ways = 0
    if A[i] > k:
        R = range(k+1)
    else:
        R = range(A[i] + 1)
    for x in R:
        ans = get_possible_ways(i+1, k-x)
        if ans > 1000000007:
            ans -= 100000007
        ways += get_possible_ways(i+1, k-x)


    possible_ways[i, k] = ways

    return ways

print get_possible_ways(0, K)

Submission status: Time Limit Exceeded

Solution code:
div = 10**9 + 7

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

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

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

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

Submission status: Time Limit Exceeded

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

def ciasteczka(): 
    N, K = wczytaj_liste()
    max_cukierkow = wczytaj_liste()
    przed = [1]
    for dziecko in max_cukierkow:
        po = [0]* min(len(przed)+ dziecko, K+1)
        for i in range(len(po)):
            for b in range(dziecko+1):
                j = i - b
                if  0 <= j < len(przed):
                    po[i] += przed[j]
                    if po[i] >= 10**9+7:
                        po[i] -= 10**9+7
        przed = po
    if K < len(przed):
        print(przed[K])
    else:
        print(0)
    
ciasteczka()

Submission status: Time Limit Exceeded

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

def ciasteczka(): 
    N, K = wczytaj_liste()
    max_cukierkow = wczytaj_liste()
    przed = [1]
    for dziecko in max_cukierkow:
        po = [0]* max(len(przed)+ dziecko, K+1)
        for i in range(len(po)):
            for b in range(dziecko+1):
                j = i - b
                if  0 <= j < len(przed):
                    po[i] += przed[j]
                    if po[i] >= 10**9+7:
                        po[i] -= 10**9+7
        przed = po
    print(przed[K])
    
ciasteczka()