Source Code
#include <bits/stdc++.h>
#define ll long long
#define go ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int const N = 1e3 + 2;
int const mod = 1e9 + 7;
int const acceptable_mask = 0b11100; // in binary : 11100
int const clear_mask = 0b11111;      // in binary : 11111
int n;
ll sum(ll x, ll y)
{
    return ((x % mod) + (y % mod)) % mod;
}
ll dp[N][N][1 << 5][2];
ll dpf(int i, int open, int mask, bool ok)
{

    if (i == n)
    {
        if (mask == acceptable_mask || ok)
        {
            return (open == 0 ? 1 : 0);
        }
        return 0;
    }
    ll &ret = dp[i][open][mask][ok];
    if (ret != -1)
    {
        return ret;
    }
    ret = 0;
    mask <<= 1;
    mask &= clear_mask;
    // close
    if (open - 1 >= 0)
    {
        ret = sum(ret, dpf(i + 1, open - 1, mask, ok || (mask == acceptable_mask)));
    }
    // open
    mask |= 1;
    ret = sum(ret, dpf(i + 1, open + 1, mask, ok || (mask == acceptable_mask)));
    return ret;
}
void solve()
{
    cin >> n;
    memset(dp, -1, sizeof(dp));
    cout << dpf(0, 0, 0, false);
}

int main()
{
    int t = 1;
    // cin>>t;
    // go;
    while (t--)
    {
        solve();
        cout << "\n";
    }
    return 0;
}
Copy
Bracket Sequence Alaa_Kaadan
GNU G++17
1661 ms
262.1 MB
Memory Limit Exceeded