[POJ] 1742 Coins.cpp

#include <cstdio>
#include <numeric>
#include <algorithm>
using namespace std;

bool dp[100005];
int num[100005];

int main()
{
    int N, M;
    int A[101], C[101];
    while (scanf("%d %d", &N, &M) && (N || M)) {
        for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
        for (int i = 0; i < N; ++i) scanf("%d", &C[i]);

        fill(dp, dp+M+1, false);
        dp[0] = true;

        for (int i = 0; i < N; ++i) {
            fill(num, num+M+1, 0);
            for (int j = 0; j+A[i] <= M; ++j)
                if (dp[j] == true && !dp[j+A[i]] && num[j] < C[i]) {
                        dp[j+A[i]] = true;
                        num[j+A[i]] = num[j] + 1;
                }
        }
        printf("%d\n", accumulate(dp+1, dp+M+1, 0)); // from dp[1] to dp[M]
    }
}