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
85
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

vector<char> rozwin_tasiemca() {
    int ile_kawaleczkow;
    char pierwszy_nawias;
    cin >> ile_kawaleczkow >> pierwszy_nawias;
    vector<ll> kluski(ile_kawaleczkow);
    for (int i = 0; i < ile_kawaleczkow; ++i) cin >> kluski[i];
    vector<char> potwor;
    ll suma = 0;
    for (ll x : kluski) suma += x;
    potwor.reserve((size_t)suma);
    char teraz = pierwszy_nawias;
    for (int i = 0; i < ile_kawaleczkow; ++i) {
        for (ll j = 0; j < kluski[i]; ++j) potwor.push_back(teraz);
        teraz = (teraz == '(' ? ')' : '(');
    }
    return potwor;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<char> sznurek_s = rozwin_tasiemca();
    vector<char> sznurek_t = rozwin_tasiemca();

    int dlugosc_s = (int)sznurek_s.size();
    int dlugosc_t = (int)sznurek_t.size();

    vector<int> prefiksowy_bigos_s(dlugosc_s + 1, 0);
    for (int i = 0; i < dlugosc_s; ++i) {
        prefiksowy_bigos_s[i + 1] = prefiksowy_bigos_s[i] + (sznurek_s[i] == '(' ? 1 : -1);
    }

    int bilans_sznurka_s = prefiksowy_bigos_s[dlugosc_s];

    long long odpowiedz_z_kapelusza = 0;

    vector<char> czy_da_sie(dlugosc_s + 1), nowa_misterna_bieda(dlugosc_s + 1), baza_po_t(dlugosc_s + 1);

    for (int start_podsznurka = 0; start_podsznurka < dlugosc_t; ++start_podsznurka) {
        int pierwszy_dol = 0;
        while (pierwszy_dol + 1 <= dlugosc_s && prefiksowy_bigos_s[pierwszy_dol + 1] >= 0) ++pierwszy_dol;
        fill(czy_da_sie.begin(), czy_da_sie.end(), 0);
        for (int i = 0; i <= pierwszy_dol; ++i) czy_da_sie[i] = 1;

        int bilans_podsznurka = 0;

        for (int koniec_podsznurka = start_podsznurka; koniec_podsznurka < dlugosc_t; ++koniec_podsznurka) {
            bilans_podsznurka += (sznurek_t[koniec_podsznurka] == '(' ? 1 : -1);

            bool cokolwiek_jeszcze_zipie = false;
            for (int i = 0; i <= dlugosc_s; ++i) {
                baza_po_t[i] = (czy_da_sie[i] && prefiksowy_bigos_s[i] + bilans_podsznurka >= 0);
            }

            bool aktywny_glut = false;
            for (int i = 0; i <= dlugosc_s; ++i) {
                if (prefiksowy_bigos_s[i] + bilans_podsznurka < 0) {
                    aktywny_glut = false;
                    nowa_misterna_bieda[i] = 0;
                } else {
                    aktywny_glut = aktywny_glut || baza_po_t[i];
                    nowa_misterna_bieda[i] = aktywny_glut;
                    if (aktywny_glut) cokolwiek_jeszcze_zipie = true;
                }
            }

            czy_da_sie.swap(nowa_misterna_bieda);

            if (!cokolwiek_jeszcze_zipie) break;

            if (bilans_podsznurka + bilans_sznurka_s == 0 && czy_da_sie[dlugosc_s]) {
                ++odpowiedz_z_kapelusza;
            }
        }
    }

    cout << odpowiedz_z_kapelusza << '\n';
    return 0;
}