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

Submission status: Wrong Answer

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]
        
        dp[i][j] %= 1000000007

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

Submission status: Wrong Answer

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)
  print(dp[k])
"""
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: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

dpt = [[0] * (K+1) for i in range(N+1)]
for i in range(K+1):
    dpt[0][i] = 1

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)

print((dpt[N][K]-dpt[N][K-1]) % (10**9+7))

Submission status: Wrong Answer

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

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

dpt = [[0] * (K+1) for i in range(N+1)]
for i in range(K+1):
    dpt[0][i] = 1

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)

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

Submission status: Wrong Answer

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[:])', cache=True)
def main(N,K,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])
        for j in range(K+1):
            dp[i][j]=(c[j+1]-c[max(0,j-a[i-1])])

    return dp[N][K]

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

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
A = list(map(int,input().split()))
mod = 10**9 + 7
if n ==1: print(0 if k> A[0] else 1)
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):
    B = [0]
    for j in range(k+1):
        B.append(B[-1] + dp[i-1][j])
        B[-1]%=mod
    for j in range(k+1):
        dp[i][j] += B[j+1]-B[max(0,j-A[i])]
        dp[i][j] %= mod
print(dp[-1][-1]%mod)

Submission status: Wrong Answer

Solution code:
from sys import stdin
mod = 10**9+7
n,k = map(int,stdin.readline().split())
arr = list(map(int,stdin.readline().split()))
dp = [[0]*(k+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1,n+1):
    lst = [0]
    for j in range(k+1):
        lst.append((lst[-1]+dp[i-1][j])%mod)
        dp[i][j] = lst[j+1]-lst[max(0,j-arr[i-1])]
print(dp[-1][-1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:

def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[N][K] = sum(OPT[N-1][K-i]) 0 <= i <= A[N]
    OPT[0][0] = 1
    N*K
    3 4
    1 2 3

1 0 0 0 0
1 1 0 0 0
1 2 2 1 0
1 3 5 6 5

OPT[3][1] = OPT[2][1]+OPT[2][0]
OPT[3][2] = OPT[2][2]+OPT[2][1]+OPT[2][0]
OPT[3][3] = OPT[2][3]+OPT
    """
    N, K = read_ints()
    A = read_ints()
    modulo = 10**9+7
    OPT = [[0]*(K+1) for _ in range(N+1)]
    for i in range(N+1):
        OPT[i][0] = 1
    for j in range(K+1):
        OPT[0][j] = 1
    for i in range(1, N+1):
        for j in range(1, K+1):
            OPT[i][j] += OPT[i][j-1]+OPT[i-1][j]
            if j-A[i-1]-1 >= 0:
                OPT[i][j] -= OPT[i-1][j-A[i-1]-1]
            OPT[i][j] %= modulo
    return (OPT[-1][-1])%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Wrong Answer

Solution code:
#dp[i][j] denotes number of ways to distribute j candies among first i
l=input().split()
n=int(l[0])
k=int(l[1])
l=input().split()
li=[int(i) for i in l]
dp=[[0 for i in range(k+1)]for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=1
for i in range(1,k+1):
    dp[0][i]=0
pref=[0 for i in range(k+1)]
sumi=0
for i in range(k+1):
    sumi+=dp[0][i]
    pref[i]=sumi
    pref[i]%=1000000007
for i in range(1,n+1):
    for j in range(1,k+1):
        howmany=li[i-1]
        left=max(0,j-howmany)
        right=j
        if(left==0):
            dp[i][j]=pref[j]
        else:
            dp[i][j]=pref[j]-pref[left-1]
    sumi=0
    for j in range(k+1):
        sumi+=dp[i][j]
        pref[j]=sumi
        pref[j]%=1000000007
print(dp[n][k])

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7

N, K, *A = map(int, open(0).read().split())

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

print(dp[K])

Submission status: Wrong Answer

Solution code:
mod=10**9+7
N,K=map(int,input().split())
a = list(map(int,input().split()))
ans=[[0 for e in range(K+1)] for f in range(N+1)]
for e in range(K+1):
 ans[1][e]=min(e+1,a[0]+1)
if N>1:
 for i in range(2,N+1):
  ans[i][0]=1
  for j in range(1,K+1):
   ans[i][j]=ans[i][j-1]+ans[i-1][j]
   if j-a[i-1]-1>=0:
    ans[i][j]-=ans[i-1][j-a[i-1]-1]
   ans[i][j]%=mod
if K==0:
 print(ans[N][K])
else:
 print(ans[N][K]-ans[N][K-1])

Submission status: Wrong Answer

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
d=[[0]*(K+2) for i in range(N+1)]
d[0]=[0]+[1]*(K+1)
m=10**9+7
for i in range(N):
    for j in range(K+1):
        d[i+1][j+1]=(d[i][j+1]-d[i][max(0,j-A[i])]+d[i+1][j])%m
print(d[-1][-1]-d[-1][-2])

Submission status: Wrong Answer

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(min(N,50)):
    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: Wrong Answer

Solution code:

MOD = int(1e9)+7


def main():
    n, K = map(int, input().split())
    a = list(map(int, input().split()))

    # dp[i][j] is the number of ways to distribute j candies to first i people
    dp = [[0]*(K+1) for i in range(n+1)]
    prefix = [[0]*(K+1) for i in range(n+1)]
    prefix[0] = [1]*(K+1)
    for i in range(1, n+1):
        for j in range(K+1):
            start = j - min(a[i-1], j)-1
            end = j
            dp[i][j] = prefix[i-1][end] - \
                (prefix[i-1][start] if start >= 0 else 0)
            prefix[i][j] = (prefix[i][j-1] + dp[i][j]) % MOD

    print(dp[n][K])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

cs_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]:
            tmp = 0
        elif i == 0:
            cs_dp[i][j] = 1
        elif i == 1:
            tmp = cs_dp[i][j - 1] - cs_dp[i - 1][j - 1] + min(1, a[j - 1])
        elif i - a[j - 1] - 1 < 0:
            tmp = cs_dp[i][j - 1]
        else:
            tmp = cs_dp[i][j - 1] - cs_dp[i - a[j - 1] - 1][j - 1]
        if i > 0:
            cs_dp[i][j] = (cs_dp[i - 1][j] + tmp)%(10**9+7)

#print(dp)
print(cs_dp[k][n] - cs_dp[k - 1][n] if k > 0 else cs_dp[k][n])

Submission status: Wrong Answer

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)]
cs_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], cs_dp[i][j] = 1, 1
        elif i == 1:
            dp[i][j] = dp[i][j - 1] + min(1, a[j - 1])
        elif i - a[j - 1] - 1 < 0:
            dp[i][j] = cs_dp[i][j - 1]
        else:
            dp[i][j] = cs_dp[i][j - 1] - cs_dp[i - a[j - 1] - 1][j - 1]
        if i > 0:
            cs_dp[i][j] = cs_dp[i - 1][j] + dp[i][j]

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

Submission status: Wrong Answer

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)]
cs_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], cs_dp[i][j] = 1, 1
        elif i == 1:
            dp[i][j] = dp[i][j - 1] + min(1, a[j - 1])
        elif i - a[j - 1] - 1 < 0:
            dp[i][j] = cs_dp[i][j - 1]
        else:
            dp[i][j] = cs_dp[i][j - 1] - cs_dp[i - a[j - 1] - 1][j - 1]
        if i > 0:
            cs_dp[i][j] = cs_dp[i - 1][j] + dp[i][j]

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
M = 10 ** 9 + 7
readline = sys.stdin.buffer.readline
N, K = map(int, readline().split())
a = np.array([int(x) for x in readline().split()], dtype=np.int64)
dp = np.zeros(K + 1, dtype=np.int64)
dp[0] = 1
for x in a:
 dp = np.cumsum(dp)
 dp[x+1:] -= dp[:-x-1]
 dp %= M
print(dp[K])

Submission status: Wrong Answer

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+1):
    dp_sum[i][0]=1

for i in range(n):
    for j in range(k+1):
        if j-1>=0:
            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])

Submission status: Wrong Answer

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



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

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

print(dp[k])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [[1]*(k+10) for _ in range(2)]
f = 1
for x in a:
  for i in range(1, k + 1):
    b[f][i] = b[f^1][i]
    if i > x:
      b[f][i] -= b[f^1][i-x-1]
    b[f][i] = (b[f][i] + b[f][i-1]) % mod
  f ^= 1
print((b[f^1][k] - b[f^1][k-1]) % mod)

Submission status: Wrong Answer

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(1,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: Wrong Answer

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(1,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: Wrong Answer

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(1,K+1):
    if j==0:
      dp[i][j]=0
    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: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    if K == 0:
        return 1
    A = list(map(int, input().split()))
    MOD = 10**9+7
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(K):
            dp[i+1][j] += dp[i][j]
            if j+a+1 <= K:
                dp[i+1][j+a+1] -= dp[i][j]
        for j in range(K):
            dp[i+1][j+1] += dp[i+1][j]
        # for j in range(K+1):
        #     dp[i+1][j] = dp[i+1][j] % MOD

    return dp[N][K] % MOD


print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    if K == 0:
        return 1
    A = list(map(int, input().split()))
    MOD = 10**9+7
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(K):
            dp[i+1][j] += dp[i][j]
            if j+a+1 <= K:
                dp[i+1][j+a+1] -= dp[i][j]
        for j in range(K):
            dp[i+1][j+1] += dp[i+1][j]
        for j in range(K+1):
            dp[i+1][j] %= MOD

    return dp[N][K]


print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    if K == 0:
        return 1
    A = list(map(int, input().split()))
    MOD = 10**9+7
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(K):
            dp[i+1][j] += dp[i][j]
            if j+a+1 <= K:
                dp[i+1][j+a+1] -= dp[i][j]
        for j in range(K):
            dp[i+1][j+1] += dp[i+1][j]
            dp[i+1][j+1] %= MOD

    return dp[N][K]


print(main())

Submission status: Wrong Answer

Solution code:
def main():
    N, K = map(int, input().split())
    if K == 0:
        return 1
    A = list(map(int, input().split()))
    MOD = 10**9+7
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        a = A[i]
        for j in range(K):
            dp[i+1][j] += dp[i][j]
            if j+a+1 <= K:
                dp[i+1][j+a+1] -= dp[i][j]
        for j in range(K):
            dp[i+1][j] %= MOD
            dp[i+1][j+1] += dp[i+1][j]

    return dp[N][K]


print(main())