Zapis

input/code.cpp: In function 'int match(char, char)':
input/code.cpp:11:15: warning: array subscript has type 'char' [-Wchar-subscripts]
     return q[a] == b;
               ^

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define debug(...) #__VA_ARGS__ << ": " << __VA_ARGS__
using ii=long long;
int n;
char d[222],q[222];
int dp[222][222][2], pd[222][222][2];
int match(char a, char b)
{
    return q[a] == b;
}
int fl(char a)
{
    return a == '(' || a == '[' || a == '{';
}
int fr(char a)
{
    return !fl(a);
}
int hae(int a, int b, int c = 3)
{
    if (b & 1) return dp[a][b][c] = 0;
    if (b == 0) return dp[a][b][c] = 1;
    if (pd[a][b][c]) return dp[a][b][c];
    pd[a][b][c] = 1;
    int r = 0;
    if (c & 1) {
        int x = hae(a + 1, b - 2);
        int ok = (d[a] == '?' && d[a + b - 1] != '?' && fr(d[a + b - 1]));
        ok |= (d[a] != '?' && d[a + b - 1] == '?' && fl(d[a]));
        ok |= (d[a] != '?' && d[a + b - 1] != '?' && match(d[a], d[a + b - 1]));
        if (ok) r = x;
        else if (d[a] == '?' && d[a + b - 1] == '?') r = 3 * x % (int) 1e5;
    }
    if (c & 2) {
        for (int i = 2; i < b; i += 2) {
            r += ((ii) hae(a, i, 1) * (ii) hae(a + i, b - i, 2)) % (ii) 1e5;
            r += ((ii) hae(a, i, 1) * (ii) hae(a + i, b - i, 1)) % (ii) 1e5;
            r %= (int) 1e5;
        }
    }
    return dp[a][b][c] = r;
}
int main()
{
    q['('] = ')';
    q['['] = ']';
    q['{'] = '}';
    cin >> n >> (d + 1);
    cout << hae(1, n) << "\n";
    return 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            for (int c = 0; c < 2; ++c) if (dp[i][j][c]) {
                printf("dp[%d][%d][%d] = %d\n", i, j, c, dp[i][j][c]);
            }
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED