PythonでJOI難易度6を埋める #8

stairs - 階段 (Stairs)

解法は思い浮んだけど，実装できず...
]を段目までの行きかたの場合の数，とすると，]はまで一回のジャンブで行ける範囲のの総和となる．の累積和を用意すれば，一回のジャンプでまで行くことができる範囲は二分探索で求めることができる．範囲が分かれば，dpの累積和から]を求めればよい．1234567の余りをとることに注意．

from bisect import bisect_left #二分探索ライブラリ

n, p = map(int, input().split())
h = [int(input()) for _ in range(n)]
mod = 1234567

csum_step = [0]
for i in range(n):
    csum_step.append(csum_step[-1] + h[i])

csum_dp = [0, 1] #0, 1段目までの行きかた

for i in range(1, n + 1): #2段目~
    low = csum_step[i] - p
    index = bisect_left(csum_step, low)

    tmp = csum_dp[i] - csum_dp[index]
    csum_dp.append((csum_dp[-1] + tmp) % mod)

print((csum_dp[-1] - csum_dp[-2]) % mod)