제출 #1323862

#제출 시각아이디문제언어결과실행 시간메모리
1323862gelastropodHomework (CEOI22_homework)C++20
0 / 100
79 ms85560 KiB
#include <bits/stdc++.h>
using namespace std;

vector<int> point;
string S;

pair<int, int> solve(int s) {
    if (S[s] == '?') return {0, 0};
    int flip = S[s + 2] == 'n';
    pair<int, int> res1, res2;
    if (S[s + 4] == '?') {
        res1 = { 0, 0 };
        s += 6;
    }
    else {
        res1 = solve(s + 4);
        s = point[s + 7] + 2;
    }
    if (S[s] == '?') res1 = { 0, 0 };
    else res2 = solve(s);
    if (flip) return { min(res1.first, res2.first), res1.second + res2.second + 1 };
    return { res1.first + res2.first + 1, min(res1.second, res2.second) };
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> S;
    int N = 0;
    point.resize(S.size(), -1);
    stack<int> idxs;
    for (int i = S.size() - 1; i >= 0; i--) {
        if (S[i] == ')') idxs.push(i);
        else if (S[i] == '(') {
            point[i] = idxs.top();
            idxs.pop();
        }
        N += S[i] == '?';
    }
    auto res = solve(0);
    cout << N - res.first - res.second << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...