5626번: 제단 - 최적화 필요

https://www.acmicpc.net/problem/5626

#include<stdio.h>
#define sosu 1000000007
int dp1[10001], dp2[10001];
int n, a[10000];
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++) scanf("%d", a + i);
    if (a[0]>0) {
        puts("0");
        return 0;
    }
    dp1[0] = 1;
    for (int i = 1; i<n; i++) {
        if (a[i] == -1) {
            dp2[0] = (dp1[0] + dp1[1]) % sosu;
            for (int j = 1; j<5000; j++)
                dp2[j] = ((dp1[j - 1] + dp1[j]) % sosu + dp1[j + 1]) % sosu;
        }
        else {
            for (int j = 0; j<5000; j++) dp2[j] = 0;
            if (a[i] == 0) dp2[0] = (dp1[0] + dp1[1]) % sosu;
            else dp2[a[i]] = ((dp1[a[i] - 1] + dp1[a[i]]) % sosu + dp1[a[i] + 1]) % sosu;
        }
        for (int j = 0; j<5000; j++) dp1[j] = dp2[j];
    }
    printf("%d", dp1[0]);
    return 0;
}