제출 #1307093

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307093		simona1230	Homework (CEOI22_homework)	C++20	23 / 100	592 ms	17468 KiB

Main

#include <bits/stdc++.h>

using namespace std;
string s;
int a[200001];
vector<int> v[200001];
int num=0,g;
void build()
{
    stack<int> h;
    for(int i=0;i<s.size();i++)
    {
        int tp=0;
        if(s[i]=='m')
        {
            if(s[i+1]=='i')a[++num]=-1;
            else a[++num]=1;

            if(h.size())
                v[h.top()].push_back(num);
            h.push(num);
        }

        if(s[i]==')')
            h.pop();

        if(s[i]=='?')
        {
            num++;
            g++;
            v[h.top()].push_back(num);
        }
    }

    /*for(int i=1;i<=num;i++)
    {
        cout<<i<<":: ";
        for(auto j:v[i])
            cout<<j<<" ";
                cout<<endl;
    }*/
}

int cnt[200001];
int dp[1024][100001];
vector<int> p[100001];

void prec()
{
    for(int i=0;i<(1<<g);i++)
    {
        p[__builtin_popcount(i)].push_back(i);
    }
}

void dfs(int i)
{
    for(auto j:v[i])
    {
        dfs(j);
        cnt[i]+=cnt[j];
    }

    if(v[i].size())
    {
        int v1=v[i][0];
        int v2=v[i][1];

        for(auto b1:p[cnt[v1]])
        {
            for(auto b2:p[cnt[v2]])
            {
                if(b1&b2)continue;
                int b=b1+b2;

                /*int curr=0;
                if(a[i]==1)
                {
                    int m1=g,m2=g;
                    for(int j=0;j<g;j++)
                    {
                        if(dp[v1][b1]&(1<<j))
                            m1=min(m1,j);
                        if(dp[v2][b2]&(1<<j))
                            m2=min(m2,j);
                    }

                    for(int j=0;j<=min(m1,m2);j++)
                    {
                        if((1<<j)&dp[v1][b1])
                            curr+=(1<<j);
                        if((1<<j)&dp[v2][b2])
                            curr+=(1<<j);
                    }
                }
                else
                {
                    int m1=0,m2=0;
                    for(int j=0;j<g;j++)
                    {
                        if(dp[v1][b1]&(1<<j))
                            m1=max(m1,j);
                        if(dp[v2][b2]&(1<<j))
                            m2=max(m2,j);
                    }

                    for(int j=max(m1,m2);j<g;j++)
                    {
                        if((1<<j)&dp[v1][b1])
                            curr+=(1<<j);
                        if((1<<j)&dp[v2][b2])
                            curr+=(1<<j);
                    }
                }

                dp[i][b]|=curr;*/

                for(int g1=0;g1<g;g1++)
                {
                    for(int g2=0;g2<g;g2++)
                    {
                        if(dp[v1][b1]&(1<<g1))
                            if(dp[v2][b2]&(1<<g2))
                        {
                            int f=min(g1,g2);
                            if(a[i]==1)f=max(g1,g2);
                            dp[i][b]|=(1<<f);
                        }
                    }
                }
            }
        }
    }
    else
    {
        cnt[i]=1;
        for(int j=0;j<g;j++)
            dp[i][(1<<j)]=(1<<j);
    }
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>s;
	build();
	prec();
	dfs(1);

	/*for(int i=1;i<=num;i++)
    {
        for(auto j:p[cnt[i]])
            cout<<i<<" "<<j<<" : "<<dp[i][j]<<endl;
    }*/

	cout<<__builtin_popcount(dp[1][(1<<g)-1])<<endl;
	return 0;
}

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