USACO 2.2.2 – Subset Sums

#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;

int main() {
	int n;
	freopen("subset.in", "r", stdin), freopen("subset.out", "w", stdout);
	scanf("%d", &n);
	long long int dp[400] = { 0 }, sum = (n * (n + 1))/2;
	dp[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int s = sum/2; s >= i; s--)
			dp[s] += dp[s - i];

	printf("%lld\n", (sum%2? 0 : dp[sum/2] / 2));
	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: