Submission #1229256

#TimeUsernameProblemLanguageResultExecution timeMemory
1229256asdfghqwertHomework (CEOI22_homework)C++20
100 / 100
130 ms167940 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 8 , MOD = 1e9 + 7 , T = 350;// Adjust N as we need nNNNn
string s;
vector<int> a;
struct range{
    int n , l , r ;
};
range solve(int l , int r){
    if(l == r)return {1 , 1 , 1};
    auto f1 = solve(l + 4 , a[l + 3] - 1);
    auto f2 = solve(a[l + 3] + 1 , r - 1);
    if(s[l + 1] == 'a'){
        return {f1.n + f2.n , f1.l + f2.l , f1.n + f2.n - min(f1.n - f1.r , f2.n - f2.r)};
    }
    return {f1.n + f2.n , min(f1.l , f2.l) , f1.r + f2.r - 1};
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> s;const int n = s.size();
    a.resize(n);
    vector<int> op;
    for(int i = 0  ;i < n;i++){
        if(s[i] == '(')op.push_back(i);
        if(s[i] == ',')a[op.back()] = i;
        if(s[i] == ')')op.pop_back();
    }
    range x = solve(0 , n - 1);
    cout << x.r - x.l + 1;
}
#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...