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;
typedef long long ll;
#define x first
#define y second
string s;
ll n=0;
ll sol1(ll a, ll b, ll c)
{
if(a==b) return c;
ll temp=a+4;ll c1=0;
while(true)
{
c1+=(s[temp]=='(');
c1-=(s[temp]==')');
if(c1==0&&s[temp]==',') break;
temp++;
}
if(s[a+2]=='n')
{
ll o1=sol1(a+4,temp-1,c);
ll o2=sol1(temp+1,b-1,c);
return min(o1,o2);
}
else
{
ll o1=sol1(a+4,temp-1,c);
ll o2=sol1(temp+1,b-1,o1+1);
return o2;
}
}
ll sol2(ll a, ll b, ll c)
{
if(a==b) return c;
ll temp=a+4;ll c1=0;
while(true)
{
c1+=(s[temp]=='(');
c1-=(s[temp]==')');
if(c1==0&&s[temp]==',') break;
temp++;
}
if(s[a+2]=='n')
{
ll o1=sol2(a+4,temp-1,c);
ll o2=sol2(temp+1,b-1,o1-1);
return o2;
}
else
{
ll o1=sol2(a+4,temp-1,c);
ll o2=sol2(temp+1,b-1,c);
return max(o1,o2);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>s;
for(auto i:s)n+=(i=='?');
cout<<sol2(0,s.size()-1,n)-sol1(0,s.size()-1,1)+1;
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... |