読者です 読者をやめる 読者になる 読者になる

JOI 2010 春合宿 day1-3 「Stairs」

JOI

累積和的な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;
}