Submission #3973752

Source Code Expand

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

Submission Info

Submission Time
Task M - Candies
User yaketake08
Language PyPy3 (2.4.0)
Score 100
Code Size 340 Byte
Status AC
Exec Time 524 ms
Memory 44748 KiB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 16
Set Name Test Cases
All 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11
Case Name Status Exec Time Memory
0_00 AC 164 ms 38384 KiB
0_01 AC 166 ms 38256 KiB
0_02 AC 165 ms 38256 KiB
0_03 AC 202 ms 44508 KiB
1_00 AC 162 ms 38256 KiB
1_01 AC 170 ms 40304 KiB
1_02 AC 165 ms 38256 KiB
1_03 AC 471 ms 44748 KiB
1_04 AC 509 ms 44012 KiB
1_05 AC 524 ms 43448 KiB
1_06 AC 514 ms 43392 KiB
1_07 AC 508 ms 43996 KiB
1_08 AC 516 ms 43484 KiB
1_09 AC 507 ms 44536 KiB
1_10 AC 502 ms 43860 KiB
1_11 AC 500 ms 44488 KiB