제출 #1323859

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

vector<int> point;

pair<int, int> solve(int idx, string s) {
    string oS = s;
    if (s == "?") return { 0, 0 };
    string func = s.substr(0, 3);
    int flip = func == "min";
    s = s.substr(4, s.size() - 5);
    int split = s.find(','), brac = s.find('(');
    pair<int, int> res1, res2;
    if (split < brac || brac == -1) {
        res1 = solve(idx + 4, s.substr(0, split));
        res2 = solve(idx + split + 5, s.substr(split + 1, string::npos));
    }
    else {
        res1 = solve(idx + 4, s.substr(0, point[brac + idx + 4] - 3 - idx));
        res2 = solve(point[brac + idx + 4] + 2, s.substr(point[brac + idx + 4] - 2 - idx, string::npos));
    }
    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);
    string s; 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, s);
    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...