CUBE-048: ร้านสะดวกซื้อ (Convenience Store)

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    int dp2[50001],dp1[50001];
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        dp1[k]=1;
        for(int j=k-1;j>=0;j--){
            if(j+x<=k) dp2[j]=dp1[j+x]+dp1[j];
            else dp2[j]=dp1[j];
            dp2[j]=dp2[j]%N;
        }
        for(int j=0;j<=k;j++) dp1[j]=dp2[j];
    }
    printf("%d",dp2[0]);

    return 0;
}