Source Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define endl "\n"
#define F first
#define S second
#define deb(x) cout<<#x<<'='<<x<<endl
#define stldeb(x) { cout<<"#v: " ;for(auto i :x){cout<<i<<' ';};cout<<endl;}
#define ii pair <int,int>
#define li pair <ll,int>
#define il pair <int,ll>
const ll Mod =1e9+7;
const ll INF=1e18+5;
vector<ll>fa(1001000);
ll add(ll x,ll y){
    ll ans=x+y;
    if(ans>Mod)
        ans-=Mod;
    return ans;
}
void add_self(int& x,int y){
    x = add(x,y);
}
ll sub(ll x,ll y){
    x %= Mod;   y %= Mod;
    return (x-y+Mod) % Mod;
}
void sub_self(ll& x,ll y){
    x = sub(x,y);
}
ll mul(ll x,ll y){
    x %= Mod;   y %= Mod;
    return x*y % Mod;
}
void mul_self(ll& x,ll y){
    x = mul(x,y);
}
ll fp(ll a, ll b) {
    ll res = 1;
    while (b > 0) {
        if (b & 1)
            res = (res * a)%Mod;
        a = (a * a) %Mod;
        b >>= 1;
        b%=Mod;
    }
    return res;
}
ll inv(ll y){
    return fp(y,Mod-2);
}
ll inv(ll x,ll y){
    return mul(x,inv(y));
}
ll sProgression(ll q,ll n){   //progression
    if(q==1)    return n;
    return inv(sub(fp(q,n),1),sub(q,1));
}
ll gcd(ll a, ll b) {
    if (!a || !b)
        return a | b;
    unsigned ll shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}
ll lcm(ll a,ll b)
{
    return (a/gcd(a,b))*b;
}
ll ecGcd(ll a, ll b, ll& x, ll& y) {//don't forget bezout's identity (x+b*k/gcd , y-a*k/gcd)
    x = 1, y = 0;                   // only 2 solution achieve |x|<b/gcd && |y|<a/gcd  ec is one of them
    ll x1 = 0, y1 = 1, a1 = a, b1 = b;//choose k to achieve some proberities
    while (b1) {
        ll q = a1 / b1;
        tie(x, x1) = make_tuple(x1, x - q * x1);
        tie(y, y1) = make_tuple(y1, y - q * y1);
        tie(a1, b1) = make_tuple(b1, a1 - q * b1);
    }
    return a1;
}
ll ldioph(ll a,ll b,ll c,ll& x,ll& y)
{
    ll g=ecGcd(a,b,x,y);
    if(c%g == 0)
        x*=c/g,y*=c/g;
    return g;
}
ll C(ll n,ll k) // Choose k from n // call calculateFactorials first
{
 if(k>n) return 0;
 return mul(mul(fa[n],inv(fa[k])),inv(fa[n-k]));
}
void calculateFactorials(int n)
{
 fa[0]=1;
 for(ll i=1; i<=n; i++)
 fa[i]=mul(fa[i-1],i);
}
const int Nsieve=1e6+10;
ll cntSieve[Nsieve];
vector<bool> isPrime(Nsieve,true);
void sieve()
{
    for(ll i=2;i<Nsieve;i++)
    {
        if(isPrime[i])
        {
            for(ll j=i*i;j<Nsieve;j+=i)
            {
                isPrime[j]=0;
            }
        }

    }

}
ll Vp(ll P ,ll N)
{
  ll X = 0;
  for(ll i = P ; i <= N ; i *= P){
    X += N / i;
  }
  return X;
}
// Define here ..

const int N=1010;
ll dp[N][N][2];
int n;
ll solve(int i,int b,int taken )
{
    if(i>n || b<0)
        return 0;
    if(i==n)
    {
        cout<<b<<' '<<taken<<endl;
        if(b==0 && taken)
            return 1;
        return 0;
    }
    ll& ret=dp[i][b][taken];
    if(ret!=-1)
        return ret;
    ret=0;
    ret=add(solve(i+1,b+1,taken),solve(i+1,b-1,taken));
    if(!taken)
        ret=add(ret,solve(i+5,b+1,1));
    return ret;
}
int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            dp[i][j][0]=dp[i][j][1]=-1;
    cin>>n;
    cout<<solve(0,0,0);
    return 0;
}

Copy
Bracket Sequence neodoomer
GNU G++17
16 ms
24.2 MB
Wrong Answer