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;
vector<int> haha[3000001];
vector<bool> bruh(3000001);
vector<pair<int,int>> dp(3000001);
void dfs(int a) {
if(haha[a].empty()) {
dp[a] = {0,0};
return;
}
dfs(haha[a][0]);
dfs(haha[a][1]);
pair<int,int> c = dp[haha[a][0]];
pair<int,int> d = dp[haha[a][1]];
if(bruh[a]) {
dp[a] = {min(c.first,d.first),c.second+d.second+1};
}
else {
dp[a] = {c.first+d.first+1,min(c.second,d.second)};
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string s;
cin >> s;
int y = 0,br = 1,n = 0;
vector<int> wut(1);
while(y < s.size()) {
if(s[y] == 'm') {
haha[wut[wut.size()-1]].push_back(br);
wut.push_back(br);
if(s[y+1] == 'i') {
bruh[br] = 1;
}
else {
bruh[br] = 0;
}
br++;
y+=4;
}
else if(s[y] == '?') {
haha[wut[wut.size()-1]].push_back(br);
n++;
br++;
y++;
}
else if(s[y] == ')') {
wut.pop_back();
y++;
}
else {
y++;
}
}
dfs(1);
cout << n-dp[1].first-dp[1].second;
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while(y < s.size()) {
| ~~^~~~~~~~~~
# | 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... |