USACO 2.3.4 – Money System


#include <cstdio>
using namespace std;

int main() {
	long long int N, V, v[26] = { 0 }, dp[10001] = { 0 }, i;
	freopen("money.in", "r", stdin), freopen("money.out", "w", stdout);
	scanf("%lld %lld", &V, &N);
	for (i = 0, dp[0] = 1; i < V; i++)
		scanf("%lld", v + i);

	for (int m = 0; m < V; m++)
		for (int n = 0; n <= N; n++)
			dp[n] += (n - v[m] >= 0 ? dp[n - v[m]] : 0);

	printf("%lld\n", dp[N]);
	return 0;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: