【USACO 2.2】Subset Sums (DP)

/*
TASK: subset
LANG: C++
*/
#include<bits/stdc++.h>
int n;
int s,ans;
long long dp[100][1000];
int main(){
    freopen("subset.in","r",stdin);
    freopen("subset.out","w",stdout);
    scanf("%d",&n);    
    for(int i=1;i<=n;i++)s+=i;
    dp[0][0]=1;
    if(s%2==0)
    for(int i=1;i<=n;i++){
        for(int j=0;j<=s/2;j++)
            dp[i][j]+=dp[i-1][j]+(j>=i?dp[i-1][j-i]:0);

    printf("%lld\n",dp[n][s/2]/2);
}