[JOI合宿]2010-Day1:Stairs

尺取り法＋DPの問題でした.
O(N)の解法です～.

眠いので詳しい解法は後日... (最近こればっかり言っていて辛い...)

#include <stdio.h>

int main(void)
{
    int i, j;
    static int dp[500001], height[500001];
    int N, P;
    int tail;
    int temp;
    int sum, step;
    
    scanf("%d%d", &N, &P);
    
    step = tail = 0;
    sum = 0;
    dp[0] = 1;
    
    for (i = 0; i < N; i++){
        scanf("%d", &height[i]);
        
        if (i != 0){
            while (step > P){
                step -= height[tail];
                sum = (sum - dp[tail++] + 1234567) % 1234567;
            }
            dp[i] = sum % 1234567;
        }
        
        step += height[i];
        
        sum = (sum + dp[i]) % 1234567;
    }
    while (step > P){
        step -= height[tail];
        sum = (sum - dp[tail++] + 1234567) % 1234567;
    }
    
    printf("%d\n", sum);
    
    return (0);
}