1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>


using namespace std;


vector <int> readSeq() {
    int n;
    cin >> n;

    char c;
    cin >> c;

    vector <int> seq;

    int curr = c == '(' ? 1 : -1;
    while (n--) {
        int x;
        cin >> x;

        seq.resize(seq.size() + x, curr);
        curr *= -1;
    }

    return seq;
}

set <pair<int,int>> ans;
vector <vector<int>> seen;

void backtrack(int i, int jStart, int j, int sum, int n, int m, vector <int> &s, vector <int> &t) {
    if (sum < 0) {
        return ;
    }

    if (seen[i][j]) {
        return ;
    }

    seen[i][j] = 1;

    if (i == n) {
        if (sum == 0 && jStart < j) {
            ans.insert({jStart, j - 1});
        }

        if (j == m) {
            return ;
        }
    }

    if (i < n) {
        backtrack(i + 1, jStart, j, sum + s[i], n, m, s, t);
    }

    if (j < m) {
        backtrack(i, jStart, j + 1, sum + t[j], n, m, s, t);
    }
}

int solve(vector <int> &s, vector <int> &t) {
    int n = s.size(), m = t.size();

    seen = vector <vector<int>> (n + 1, vector <int> (m + 1, 0));

    for (int j = 0; j < m; j++) {
        backtrack(0, j, j, 0, n, m, s, t);

        for (int x = 0; x <= n; x++) for (int y = 0; y <= m; y++) {
            seen[x][y] = 0;
        }
    }

    return ans.size();
}

int main() {
    ios_base::sync_with_stdio(false);

    auto s = readSeq(), t = readSeq();
    cout << solve(s, t);

    return 0;
}