USACO-T027: Subset Sums

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

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

typedef long long lli;

const int N = 39 + 5;
const int X = 39 * 40 / 4 + 5;

lli dp[N][X];

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

    int n;
    scanf("%d", &n);
    int sum = n * (n + 1) / 2;
    if(sum % 2 == 1){
        cout << "0\n";
        fclose(stdin);
        fclose(stdout);
        return 0;
    }
    int tr = sum / 2;
    for(int i = 1; i <= n + 1; ++i){
        dp[i][0] = 1;
    }
    for(int i = n; i >= 1; --i){
        for(int t = 1; t <= tr; ++t){
            if(t >= i){
                dp[i][t] = dp[i + 1][t - i] + dp[i + 1][t];
            } else {
                dp[i][t] = dp[i + 1][t];
            }
        }
    }
    cout << dp[1][tr] / 2 << '\n';

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