UVa 986 - How Many?

986.cpp

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

#define F first
#define S second
#define endl '\n'
#define PB push_back

typedef long long ll;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef pair<int, char> ic;

const int oo = ~(1<<31);

int n, r, k;
int dp[44][24][24][2];

int sol = 0;
int f(int i, int j, int z, int d) {

    if(z < 0) return 0;
    if(!i && !j && !z) return 1;
    if(!i) return 0;

    if(~dp[i][j][z][d])
        return dp[i][j][z][d];

    int &r = dp[i][j][z][d];
    r = 0;

    if(j == k && d) {
        r += f(i - 1, j - 1, z - 1, 0);
        r += f(i - 1, j + 1, z, 1);
    }else if(!j) {
        r += f(i - 1, j + 1, z, 1);
    } else if(j == 19) {
        r += f(i - 1, j - 1, z, 0);
    } else {
        r += f(i - 1, j - 1, z, 0);
        r += f(i - 1, j + 1, z, 1);
    }

    return r;
}

int main() {

    #ifndef CBDAVIDES
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
    #endif

    while(cin >> n >> r >> k) {
        n <<= 1;
        memset(dp, -1, sizeof dp);

        cout << f(n, 0, r, 0) << endl;
    }

    return 0;
}