Submission #145715

#	Time	Username	Problem	Language	Result	Execution time	Memory
145715		MKopchev	parentrises (BOI18_parentrises)	C++14	100 / 100	351 ms	216040 KiB

parentrises

#include<bits/stdc++.h>
using namespace std;
const int nmax=1e6+42,mod=1e9+7,LIM=302;
char output[nmax];
stack<int> idle;

int dp[LIM][LIM][LIM][2];
int rec(int pos,int all_open_brackets,int open_now,int mode)
{
    if(mode==0)
    {
        if(pos==0)return open_now==0;
        if(dp[pos][all_open_brackets][open_now][mode]!=-1)return dp[pos][all_open_brackets][open_now][mode];

        int ret=rec(pos-1,all_open_brackets+1,open_now+1,mode);//add '('
        //add ')'
        if(open_now)
            ret=ret+rec(pos-1,all_open_brackets,open_now-1,mode);
        else if(all_open_brackets)
        {
            //remain in mode 0
            ret=(ret+rec(pos-1,all_open_brackets-1,open_now,mode))%mod;
            //go to mode 1
            ret=(ret+rec(pos-1,0,0,1))%mod;
        }
        ret=ret%mod;
        dp[pos][all_open_brackets][open_now][mode]=ret;
        return ret;
    }
    //mode=1
    if(pos==0)return all_open_brackets==0;
    if(dp[pos][all_open_brackets][open_now][mode]!=-1)return dp[pos][all_open_brackets][open_now][mode];
    int ret=0;
    //add '('
    ret=ret+rec(pos-1,all_open_brackets+1,open_now+1,1);
    //add ')'
    if(open_now)
    {
        ret=ret+rec(pos-1,max(all_open_brackets-2,0),open_now-1,1);
    }
    ret=ret%mod;
    dp[pos][all_open_brackets][open_now][mode]=ret;
    return ret;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();

    int p,t;
    cin>>p>>t;

    if(p==1)
    {
        string s;
        for(int i=1;i<=t;i++)
        {
            cin>>s;
            int SZ=s.size();
            for(int j=0;j<SZ;j++)
                output[j]=-1;

            stack<int> open=idle;
            for(int j=0;j<SZ;j++)
            {
                if(s[j]=='(')open.push(j);
                else
                {
                    if(open.size())
                    {
                        output[open.top()]='R';
                        output[j]='R';
                        open.pop();
                    }
                }
            }

            bool ok=1;

            open=idle;
            for(int j=0;j<SZ;j++)
            {
                if(s[j]=='(')open.push(j);
                else
                {
                    if(output[j]==-1)
                    {
                        if(open.size()==0)ok=0;
                        else
                        {
                            output[j]='B';
                            output[open.top()]='G';
                            open.pop();
                        }
                    }
                }
            }

            open=idle;
            for(int j=SZ-1;j>=0;j--)
            {
                if(s[j]==')')open.push(j);
                else
                {
                    if(output[j]==-1)
                    {
                        if(open.size()==0)ok=0;
                        else
                        {
                            output[j]='B';
                            output[open.top()]='G';
                            open.pop();
                        }
                    }
                }
            }

            if(ok)
            {
                for(int j=0;j<SZ;j++)cout<<output[j];
                cout<<endl;
            }
            else cout<<"impossible"<<endl;
        }
    }
    else
    {
        memset(dp,-1,sizeof(dp));
        int n;
        for(int i=1;i<=t;i++)
        {
            cin>>n;
            cout<<rec(n,0,0,0)<<endl;
        }
    }
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 6 / 6
• Subtask 4: 28 / 28
• Subtask 5: 6 / 6
• Subtask 6: 16 / 16
• Subtask 7: 28 / 28