Stairs

stairs.cpp

#include <cstdio>
#include <cstring>

int diffs[500001];
int a[500002];

main(){
	int n,power;
	
	scanf("%d%d",&n,&power);
	
	memset(a,0,sizeof(a));
	for(int i=0;i<n;i++) scanf("%d", diffs+i);
	
	int len = 0;
	int top = 0;
	int bottom = 0;
	int num = 0;
	
	a[0] = 1;
	for(;top < n;top++){
		num += a[top];
		len += diffs[top];
		for(;len > power; len-=diffs[bottom],num-=a[bottom],++bottom);
		a[top+1] = num = num%1234567;
	}
	
	if(a[n]<0) a[n]+=1234567;
	
	printf("%d\n", a[n]);
}