This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(51);
#define ll long long
#define pb push_back
#define ld long double
const int INF = 1e9;
string s;
vector<int> go;
int n;
int solve(int l, int r) {
if (s[l] == '?') {
return 1;
}
int i = go[l + 3];
if (s[l + 1] == 'a') {
return min(solve(l + 4, i - 1), solve(i + 1, r - 1));
} else {
return solve(l + 4, i - 1) + solve(i + 1, r - 1);
}
}
int solve2(int l, int r) {
if (s[l] == '?') {
return 1;
}
int i = go[l + 3];
if (s[l + 1] == 'a') {
return solve2(l + 4, i - 1) + solve2(i + 1, r - 1);
} else {
return min(solve2(l + 4, i - 1), solve2(i + 1, r - 1));
}
}
signed main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif // LOCAL
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> s;
n = s.size();
go.resize(n);
deque<pair<int,int>> q;
int cnt = 1;
for (int i = n - 1; i >= 0; i--) {
if (s[i] == ')') {
q.pb({i, -1});
cnt++;
} else if (s[i] == ',') {
q.back().second = i;
} else if (s[i] == '(') {
go[i] = q.back().second;
q.pop_back();
}
}
int mx = cnt - solve(0, n - 1) + 1;
int mn = solve2(0, n - 1);
cout << mx - mn + 1 << endl;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |