累積和的なDP
結構シンプルにまとまって気持ちいい。
僕は、DP萌え ですね^^
#include<cstdio> #define rrep(i,n) for(int i = 1; i <= n; i++) using namespace std; const int mod = 1234567; int dp[500002], h[500001]; int main(){ int n, p, l = 0, sumh; scanf("%d%d",&n,&p); sumh = 0; dp[0] = 0; dp[1] = 1; rrep(i,n){ scanf("%d",&h[i]); sumh += h[i]; while(sumh > p){ l++; sumh -= h[l];} dp[i+1] = (dp[i]*2 - dp[l] + mod) % mod; } printf("%d\n",(dp[n+1] - dp[n] + mod) % mod); return 0; }