Submission #929254

#	Time	Username	Problem	Language	Result	Execution time	Memory
929254		a_l_i_r_e_z_a	Homework (CEOI22_homework)	C++17	100 / 100	77 ms	35896 KiB

Main

// Be name Khoda
// Khodaya khodet komak kon
// Hope is last to die

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

#define pb push_back
#define S second
#define F first
#define mp make_pair
#define smax(x, y) (x) = max((x), (y))
#define smin(x, y) (x) = min((x), (y))
#define all(x) (x).begin(), (x).end()
#define set_dec(x) cout << fixed << setprecision(x);
#define kill(x) cout << x << endl, exit(0)
#define sz(x) ((int)(x).size())
#define file_io freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

const ll maxN = 1e6 + 10;
const ll inf = 1e9 + 7;
stack<ll> op;
stack<pll> dp;
stack<ll> cnt;

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    string s; cin >> s;
    ll n = sz(s);

    for(int i = 0; i < n; i++){
        if(s[i] == 'm'){
            if(s[i + 1] == 'a') op.push(1);
            else op.push(0);
            i = i + 2;
        }
        else if(s[i] == '?'){
            dp.push(mp(1, 1));
            cnt.push(1);
        }
        else if(s[i] == ')'){
            ll operate = op.top();
            op.pop();

            pll r = dp.top();
            dp.pop();
            pll l = dp.top();
            dp.pop();

            ll cnt_r = cnt.top();
            cnt.pop();
            ll cnt_l = cnt.top();
            cnt.pop();
            
            if(operate){
                dp.push(mp(r.F + l.F, max(cnt_l + r.S, cnt_r + l.S)));
            }
            else{
                dp.push(mp(min(l.F, r.F), l.S + r.S - 1));
            }
            cnt.push(cnt_r + cnt_l); 
        }
    }

    pll ans = dp.top();

    cout << ans.S - ans.F + 1 << '\n';

    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34