CF 629C Famil Door and Brackets ( DP )

dp( a, b ) = the number of combinations, having a characters of valid prefix bracket sequence, and the opening bracket - closing = b
dp2( a, b ) = the number of combinations, having a characters of valid suffix bracket sequence, and the closing bracket - opening = b
i = number of characters in left string, j = number of characters in right string
op_cl = opening brackets - closing brackets in string s
mxcl_op = max of ( closing brackets - opening brackets ) in prefix( s )
The answer would be
SUM( dp[ i ][ k ] * dp2[ j ][ k + op_cl ] Ɐ i ≤ n - m & k ≥ mxcl_op )
Notice that dp() and dp2() do actually give the same, so pre-calculating either of them will do fine.

#include <bits/stdc++.h>
using namespace std;
const int MAXN_M = 2000 + 2;
const int MAXM = 1e5 + 5;
const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
typedef long long ll;
const ll INF = MOD + MOD;

int n, m;
string s;

ll dp[MAXN_M][MAXN_M];
void solve(){
    dp[0][0] = 1;
    for(int i = 0; i < 2000; ++i)
        for(int j = 0; j <= 2000; ++j){
            if( j - 1 >= 0 )
                ( dp[i + 1][j - 1] += dp[i][j] ) %= MOD;
            if( j + 1 <= 2000 )
                ( dp[i + 1][j + 1] += dp[i][j] ) %= MOD;
        }
    int op_cl = 0, mxcl_op = 0;
    for(int i = 0; i < m; ++i){
        if( s[ i ] == '(' ) ++op_cl;
        else --op_cl;
        mxcl_op = max<int>( mxcl_op, -op_cl );
    }
    ll ans = 0;
    for(int i = 0; i <= n - m; ++i){
        int j = n - m - i;
        for(int x = 0; x + mxcl_op <= 2000 && x + op_cl + mxcl_op <= 2000; ++x)
            ( ans += dp[i][x + mxcl_op] * dp[j][x + op_cl + mxcl_op] ) %= MOD;
    }
    ans %= MOD; ans += MOD; ans %= MOD;
    cout << ans << endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> s;
    solve();
    return 0;
}