Submission #1148769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148769		ace5	Homework (CEOI22_homework)	C++20	100 / 100	656 ms	228520 KiB

Main

#include <bits/stdc++.h>

using namespace std;

string s;

map<int,int> iv;

vector<int> res(int l,int r)
{
    if(l == r)
        return {0,0,1};
    else
    {
        vector<int> lp = res(l + 4,iv[l+1]-1);
        vector<int> rp = res(iv[l+1]+1,r-1);
        if(s[l+1] == 'i')
            return {min(lp[0],rp[0]),lp[1] + rp[1],lp[2] + rp[2]};
        else
            return {lp[0] + rp[0] + 1,max(lp[1] + rp[2],lp[2] + rp[1]),lp[2] + rp[2]};
    }
}

int main()
{
    cin >> s;
    vector<int> st;
    for(int i = 0;i < s.size();++i)
    {
        if(s[i] == 'i')
        {
            st.push_back(i);
        }
        else if(s[i] == 'a')
            st.push_back(i);
        else if(s[i] == ',')
        {
            iv[st.back()] = i;
            st.pop_back();
        }
    }
    vector<int> ans = res(0,s.size()-1);
    cout << ans[1]-ans[0]+1;
}

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