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

Submission status: Time Limit Exceeded

Solution code:
def p_m():
    n, k = map(int, input().split())
    *a, = map(int, input().split())
    mod = 10 ** 9 + 7
    # dp[i][j]はi番目の子にj個の飴を配る方法が何通りかどうか
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    count = 0
    for i in range(n):
        for j in range(min(k + 1, count + 1)):
            count += a[i]
            for m in range(a[i] + 1):
                if j + m > k:
                    break
                dp[i + 1][j + m] += dp[i][j]
                dp[i + 1][j + m] %= mod
    print(dp[n][k])


if __name__ == '__main__':
    p_m()

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

print(dp[-1][-1]%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) for i 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][j-1]+dp[i-1][j]-dp[i-1][j-1-a[i-1]]
            dp[i][j]%mod
        
        else:
            dp[i][j]=dp[i][j-1]+dp[i-1][j]   
            dp[i][j]%mod

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

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

print(dp[-1][-1]%(10**9+7))

Submission status: Time Limit Exceeded

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

dp_list = [ 0 for i in range(k+1) ]
dp_list[0] = 1

for i in range(n):
    new_dp_list = [ 0 for i in range(k+1) ]
    for j in range(k+1):
        for h in range(a_list[i]+1):
            if j+h <= k:
                new_dp_list[j+h] += dp_list[j]
    dp_list = [ i % mod for i in new_dp_list ]

print(dp_list[-1])

Submission status: Time Limit Exceeded

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    lt= [1 if a[0] >= j else 0 for j in range(K+1)]
    s = a[0]
    for i in range(1,N):
        lt, l = l, lt
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] = t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] = t
    return l[-1] % (10 ** 9 + 7)
            
print(main())

Submission status: Time Limit Exceeded

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    s = a[0]
    for i in range(1,N):
        lt = l
        l = [0] * (K + 1)
        s += a[i]
        l[0] = 1
        t = 1
        for j in range(1, a[i]+1):
                t += lt[j]
                l[j] += t
        for j in range(a[i]+1, min(K+1, s+1)):
                t += (lt[j] - lt[j - a[i] - 1])
                l[j] += t
    return l[-1] % (10 ** 9 + 7)
            
print(main())

Submission status: Time Limit Exceeded

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

def main():
    l = [1 if a[0] >= j else 0 for j in range(K+1)]
    s = a[0]
    for i in range(1,N):
        t = 0
        lt = l
        l = [0] * (K + 1)
        s += a[i]
        for j in range(min(K+1, s+1)):
            if j == 0:
                t = 1
                l[j] = 1
            else:
                if j <= a[i]:
                    t += lt[j]
                else:
                    t += (lt[j] - lt[j - a[i] - 1])
                l[j] += t
    return l[-1] % (10 ** 9 + 7)
            
print(main())

Submission status: Time Limit Exceeded

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

def main():
    l = [0] * (K+1)
    for i in range(N):
        t = 0
        lt = l
        l = [0] * (K + 1)
        for j in range(K+1):
            if i == 0:
                if a[i] >= j:
                    l[j] = 1
            elif j == 0:
                t = 1
                l[j] = 1
            else:
                if j <= a[i]:
                    t += lt[j]
                else:
                    t += (lt[j] - lt[j - a[i] - 1])
                l[j] += t
    return l[-1] % (10 ** 9 + 7)
            
print(main())

Submission status: Time Limit Exceeded

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

def main():
    l = [[0] * (K+1) for _ in range(N)]
    for i in range(N):
        t = 0
        for j in range(K+1):
            if i == 0:
                if a[i] >= j:
                    l[i][j] = 1
            elif j == 0:
                t = 1
                l[i][j] = 1
            else:
                if j <= a[i]:
                    t += l[i - 1][j]
                else:
                    t += (l[i - 1][j] - l[i - 1][j - a[i] - 1])
                l[i][j] += t
    return l[-1][-1] % (10 ** 9 + 7)
            
print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n, k = map(int, input().split())
    aa = list(map(int, input().split()))
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, a in enumerate(aa):
        dpi1 = dp[i + 1]
        s = 0
        for j in range(k + 1):
            s += dpi[j]
            if j - a - 1 >= 0: s -= dpi[j - a - 1]
            s %= md
            dpi1[j] = s
        dpi = dpi1
    # p2D(dp)
    print(dp[n][k])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def main():
    md = 10 ** 9 + 7
    n, k = map(int, input().split())
    aa = list(map(int, input().split()))
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        a = aa[i]
        s = 0
        for j in range(k + 1):
            s += dp[i][j]
            if j - a - 1 >= 0: s -= dp[i][j - a - 1]
            s %= md
            dp[i + 1][j] = s
    # p2D(dp)
    print(dp[n][k])

main()

Submission status: Time Limit Exceeded

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class BIT:
    def __init__(self, n):
        # 0-indexed
        self.size = n
        self.tree = [0] * (n+1)
 
    def sum(self, i):
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s
    
    # 区間和の取得 [l, r)
    def get(self, l, r=None):
        if r is None: r = l+1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    # 値の追加：添字, 値
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

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

# dp[この子までの範囲で][飴を配る総数] = 場合の数
# dpの2次元目をBITで構築する
dp = [BIT(K+1) for i in range(N+1)]
dp[0].add(0, 1)

for i in range(N):
    for j in range(K+1):
        # iが送る予定の長さに応じた区間和を取る
        sm = dp[i].get(max(j-aN[i], 0), j+1) % MOD
        dp[i+1].add(j, sm)

print(dp[N].get(K) % MOD)

Submission status: Time Limit Exceeded

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

import sys
from operator import add

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

class SegTree:
    """
    以下のクエリを処理する
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """
 
    def __init__(self, n, func, init):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param init: 要素の初期値(単位元)
        """
        self.n = n
        self.func = func
        self.init = init
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.init] * (n2 << 1)
 
    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 1:
            self.tree[i >> 1] = x = self.func(x, self.tree[i ^ 1])
            i >>= 1
 
    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.init
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

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

# dp[この子までの範囲で][飴を配る総数] = 場合の数
# dpの2次元目をBITで構築する
dp = [SegTree(K+1, add, 0) for i in range(N+1)]
dp[0].update(0, 1)

for i in range(N):
    for j in range(K+1):
        # iが送る予定の長さに応じた区間和を取る
        sm = dp[i].query(max(j-aN[i], 0), j+1) % MOD
        dp[i+1].update(j, sm)

print(dp[N].query(K, K+1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
def f(k, A):
    n = len(A)

    prev = [0] * (k + 1)
    cur = [0] * (k + 1)

    # init for last column
    for j in range(min(A[n - 1], k) + 1):
        prev[j] = 1

    for i in range(n - 2, -1, -1):
        kount = 0
        for j in range(k + 1):
            # dp[i][j] = SUM dp[i - 1][ ...A[i] items before j...]
            kount += prev[j]
            if j > A[i]:
                kount -= prev[j - A[i] - 1]
            cur[j] = kount
        prev, cur = cur, prev

    return prev[-1] % 1000000007

assert f(4, [2, 3]) == 2
assert f(4, [1, 2, 3]) == 5
assert f(10, [9]) == 0
assert f(0, [0, 0]) == 1
#assert f(100000, [100000, 100000, 100000, 100000]) == 665683269

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

Submission status: Time Limit Exceeded

Solution code:
def f(k, A):
    n = len(A)
    dp = [ [0] * (k+1) for _ in range(n) ]

    # init for last column
    for j in range(min(A[n - 1] + 1, k + 1)):
        dp[n - 1][j] = 1

    for i in range(n - 2, -1, -1):
        kount = 0
        for j in range(k + 1):
            # dp[i][j] = SUM dp[i - 1][ ...A[i] items before j...]
            # start = j - A[i]
            # if start < 0:
            #     start = 0
            # X = dp[i + 1][start:j + 1]
            # count = sum(X)
            kount += dp[i+1][j]
            if j > A[i]:
                kount -= dp[i+1][j - A[i] - 1]
#            assert kount == count
            assert dp[i][j] == 0
            dp[i][j] = kount

    return dp[0][-1] % 1000000007

assert f(4, [2, 3]) == 2
assert f(4, [1, 2, 3]) == 5
assert f(10, [9]) == 0
assert f(0, [0, 0]) == 1
assert f(100000, [100000, 100000, 100000, 100000]) == 665683269

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

Submission status: Time Limit Exceeded

Solution code:
mod = 10 ** 9 + 7

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

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

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

for i in range(N):
    for j in range(K+1):
        if j == 0:
            dp[i][j] = 1
            continue
        if i == 0:
            if j <= a[i]:
                dp[i][j] = 1
            else:
                dp[i][j] = 0
            continue
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
        if j > a[i]:
            dp[i][j] -= dp[i-1][j-1-a[i]]
        if dp[i][j] > mod:
            dp[i][j] -= mod

print(dp[N-1][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 = [[0] * (K + 1) for _ in range(N + 1)]  # dp[child][candy] 残りcandy個の場合の数
dp[0][K] = 1

for child in range(1, N + 1):
    sumDp = [0] * (K + 2)
    for i in range(1, K + 2)[:: -1]:
        sumDp[i - 1] += sumDp[i] + dp[child - 1][i - 1]

    for candy in range(K + 1):
        dp[child][candy] = (sumDp[candy] - sumDp[min(K, candy + A[child - 1]) + 1]) % MOD

print(dp[N][0] % MOD)

Submission status: Time Limit Exceeded

Solution code:
N, K = map(int, input().split())
a = [int(x) for x in input().split()]
mod = 10**9+7
dp = [[0] * (K+1) for i in range(N+1)]
for i in range(K+1):
    dp[0][i] = 1
for i in range(1, N+1):
    for j in range(K+1):
        tmp = 0 if j-a[i-1]-1 < 0 else dp[i-1][j-a[i-1]-1]
        dp[i][j] += dp[i-1][j]-tmp
        dp[i][j] %= mod
    if i != N:
        for j in range(K):
            dp[i][j+1] = (dp[i][j+1]+dp[i][j])%mod
print(dp[N][K])

Submission status: Time Limit Exceeded

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

MOD = 1e9+7

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


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

dp[n][0]=1

prefix = [[0]*(k+1) for i in range(n+1)]
# prefix[n][0]=1
for kk in range(k+1):
    prefix[n][kk]=1

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



print(int(dp[0][k]%int(MOD)))

Submission status: Time Limit Exceeded

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

import sys
import numpy as np

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD
def lcm(x, y): return (x * y) // gcd(x, y)
def lcm_list(nums): return reduce(lcm, nums, 1)
def gcd_list(nums): return reduce(gcd, nums, nums[0])
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

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

# dp[この子までの範囲で][飴を配る総数] = 場合の数
dp = np.zeros((N+1, K+1), dtype=np.int64)
# 0番目まで(誰もいない)の範囲で0個配る場合の数は1通り
dp[0,0] = 1

for i, a in enumerate(A):
    for k in range(a+1):
        # k個配る場合をまとめて遷移
        dp[i+1,k:K+1] += dp[i,:K+1-k]
        dp[i+1,k:K+1] %= MOD

print(dp[N][K])

Submission status: Time Limit Exceeded

Solution code:
def main():
  M=10**9+7
  n,k,*a=map(int,open(0).read().split())
  b=[1]+[0]*k
  for i in a:
    t,d=0,[]
    for w,v in zip([0]*-~i+b,b):
      t+=v-w
      t%=M
      d+=t,
    b=d
  print(t)
main()