| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1194585 | Zbyszek99 | Homework (CEOI22_homework) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define vi vector<int>
#define vl vector<long long>
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct dp
{
pll dp[3];
};
string s;
int close[1000'001];
int n;
dp calc(int l, int r, int type)
{
vector<dp> dps;
rep2(i,l,r)
{
if(s[i] == '?')
{
dp new_dp;
new_dp.dp[0] = {1,1};
new_dp.dp[1] = {0,0};
new_dp.dp[2] = {0,0};
dps.pb(new_dp);
}
if(s[i] == 'm')
{
if(s[i+1] == 'a')
{
dps.pb(calc(i+4,close[i+3]-1,1));
}
else
{
dps.pb(calc(i+4,close[i+3]-1,0));
}
i = close[i+3];
}
}
dp ans;
vi max_sum[3];
vi min_sum[3];
if(type == 0)
{
rep(d,3)
{
ans.dp[d] = {1e9,-1e9};
max_sum[d].pb(0);
min_sum[d].pb(0);
forall(it,dps)
{
if(d == 0)
{
max_sum[d].pb(max_sum[d].back() + max(it.dp[0].ss,it.dp[2].ss));
min_sum[d].pb(min_sum[d].back() + min(it.dp[0].ff,it.dp[2].ff));
}
if(d == 1)
{
max_sum[d].pb(max_sum[d].back() + it.dp[2].ss);
min_sum[d].pb(min_sum[d].back() + it.dp[2].ff);
}
if(d == 2)
{
max_sum[d].pb(max_sum[d].back() + it.dp[2].ss);
min_sum[d].pb(min_sum[d].back() + it.dp[2].ff);
}
}
}
}
else
{
rep(d,3)
{
ans.dp[d] = {1e9,-1e9};
max_sum[d].pb(0);
min_sum[d].pb(0);
forall(it,dps)
{
if(d == 0)
{
max_sum[d].pb(max_sum[d].back() + it.dp[0].ss);
min_sum[d].pb(min_sum[d].back() + it.dp[0].ff);
}
if(d == 1)
{
max_sum[d].pb(max_sum[d].back() + it.dp[0].ss);
min_sum[d].pb(min_sum[d].back() + it.dp[0].ff);
}
if(d == 2)
{
max_sum[d].pb(max_sum[d].back() + max(it.dp[0].ss,it.dp[2].ss));
min_sum[d].pb(min_sum[d].back() + min(it.dp[0].ff,it.dp[2].ff));
}
}
}
}
rep(i,siz(dps))
{
rep(d,3)
{
ans.dp[d].ff = min(ans.dp[d].ff,dps[i].dp[d].ff + min_sum[d][i] + min_sum[d].back() - min_sum[d][i+1]);
ans.dp[d].ss = max(ans.dp[d].ss,dps[i].dp[d].ss + max_sum[d][i] + max_sum[d].back() - max_sum[d][i+1]);
}
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random();
cin >> s;
stack<int> st;
n = siz(s);
rep(i,n)
{
if(s[i] == '(')
{
st.push(i);
}
if(s[i] == ')')
{
close[st.top()] = i;
st.pop();
}
}
dp d = (s[1] == 'a' ? calc(4,n-2,1) : calc(4,n-2,0));
cout << d.dp[1].ss - d.dp[1].ff+1 << "\n";
}