Submission #1090250

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090250		ASN49K	W (RMI18_w)	C++14	25 / 100	702 ms	448 KiB

w

#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int add(int x,int y)
{
    return (x+y)%mod;
}
int prod(int x,int y)
{
    return (1LL*x*y)%mod;
}
void add_self(int& x,int y)
{
    x+=y;
    x%=mod;
}

const int MASK=(1<<5);
int bit_k(int x,int k)
{
    return (x>>k)&1;
}

int main()
{
    int n;
    cin>>n;
    vector<int>dp(MASK,0);
    dp[0]=1;
    for(int step=0;step<n;step++)
    {
        for(int mask=MASK-1;mask>0;mask--)
        {
            vector<int>bit;
            for(int j=0;j<5;j++)
            {
                bit.push_back(bit_k(mask,j));
            }
            int rez=0;
            if(!((bit[0] && !bit[1]) ||
               (bit[2] && !bit[1]) ||
               (bit[2] && !bit[3]) ||
               (bit[4] && !bit[3]))
            )
            {
                for(int j=0;j<5;j++)
                {
                    if(bit[j])
                    {
                        add_self(rez , dp[mask^(1<<j)]);
                    }
                }

                int nr=0;
                nr+=bit[0];
                nr+=bit[4];
                nr+=(bit[2]==0 && bit[1]==1);
                nr+=(bit[2]==0 && bit[3]==1);
                add_self(rez , prod(dp[mask] , nr));
            }

            dp[mask]=rez;
        }
        dp[0]=0;
    }
    //cout<<dp[11]<<' ';
    cout<<dp[MASK-1];
    return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 25 / 30
• Subtask 3: 0 / 50