oj.uz

Submission #1090258

# Submission time Handle Problem Language Result Execution time Memory
1090258 2024-09-18T05:54:58 Z ASN49K W (RMI18_w) C++14
30 / 100
 159 ms 600 KB 
#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;
}
vector<int>masks={31,30,27,26,24,15,14,11,10,8,3,2};
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(5);
            for(int j=0;j<5;j++)
            {
                bit[j]=(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[MASK-1];
    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 24 ms 444 KB Output isn't correct
4 Incorrect 142 ms 348 KB Output isn't correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 15 ms 448 KB Output is correct
4 Correct 50 ms 348 KB Output is correct
5 Correct 96 ms 352 KB Output is correct
6 Correct 145 ms 344 KB Output is correct

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Incorrect 0 ms 448 KB Output isn't correct
3 Incorrect 0 ms 356 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Incorrect 3 ms 452 KB Output isn't correct
7 Incorrect 5 ms 360 KB Output isn't correct
8 Incorrect 48 ms 352 KB Output isn't correct
9 Incorrect 96 ms 424 KB Output isn't correct
10 Incorrect 159 ms 348 KB Output isn't correct