USACO-T033: Money Systems

/*
ID: mickyta1
TASK: money
LANG: C++
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long lli;

const int N = 1e4 + 5;
const int V = 25 + 5;

lli dp[V][N];
int coin[V];

int main(){
    freopen("money.in", "r", stdin);
    freopen("money.out", "w", stdout);

    int nCoin, money;
    scanf("%d%d", &nCoin, &money);
    for(int i = 1; i <= nCoin; ++i){
        scanf("%d", &coin[i]);
    }
    for(int i = 1; i <= nCoin + 1; ++i){
        dp[i][0] = 1;
    }
    for(int i = nCoin; i >= 1; --i){
        for(int x = 1; x <= money; ++x){
            if(x >= coin[i]){
                dp[i][x] = dp[i][x - coin[i]] + dp[i + 1][x];
            } else {
                dp[i][x] = dp[i + 1][x];
            }
        }
    }
    cout << dp[1][money] << '\n';

    fclose(stdin);
    fclose(stdout);
    return 0;
}