제출 #1351900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1351900		That_Salamander	Homework (CEOI22_homework)	C++20	100 / 100	89 ms	13336 KiB

Main

#include <bits/stdc++.h>

using namespace std;

struct dp_val {
    int sz;
    int mn, mx;
};

string s;
stack<dp_val> st;

int main() {
    cin >> s;

    for (int i = s.size()-1; i>=0; i--) {
        char c = s[i];
        
        if (c == '(' || c == ')' || c == 'm' || c == 'i' || c == 'a' || c == ',') continue;
        
        if (c == '?') {
            st.push({1, 0, 0});
        } else {
            if (c == 'n') {
                dp_val left = st.top(); st.pop();
                dp_val right = st.top(); st.pop();
                
                st.push({
                    left.sz + right.sz,
                    min(left.mn, right.mn),
                    left.mx + right.mx
                });
            } else if (c == 'x') {
                dp_val left = st.top(); st.pop();
                dp_val right = st.top(); st.pop();

                st.push({
                    left.sz + right.sz,
                    left.mn + right.mn + 1,
                    max(left.sz + right.mx, right.sz + left.mx)
                });
            }
        }
    }

    cout << st.top().mx - st.top().mn + 1 << "\n";
}

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