Submission #1055417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055417		Hazard	Binaria (CCO23_day1problem1)	Cpython 3	0 / 25	9 ms	2908 KiB

Main

def count_strings(N, K, sms):
    MOD = 10**6 + 3
    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 i < K:
                dp[i+1][j+1] += dp[i][j]
                dp[i+1][j] += dp[i][j]
            else:
                target = sms[i-K+1]
                if j >= target:
                    dp[i+1][j-target+1] += dp[i][j]
                dp[i+1][j] += dp[i][j]
            dp[i+1][j+1] %= MOD
            dp[i+1][j] %= MOD

    ans = 0
    for i in range(K+1):
        ans += dp[N][i]
        ans %= MOD

    return ans

N, K = map(int, input().split())
sms = list(map(int, input().split()))
print(count_strings(N, K, sms))

• Subtask 1: 0 / 3
• Subtask 2: 0 / 3
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 7