oj.uz

Submission #1090250

# Submission time Handle Problem Language Result Execution time Memory
1090250 2024-09-18T05:51:24 Z ASN49K W (RMI18_w) C++14
25 / 100
 600 ms 448 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;
}

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Incorrect 112 ms 348 KB Output isn't correct
4 Execution timed out 702 ms 348 KB Time limit exceeded

Subtask #2
25.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 67 ms 420 KB Output is correct
4 Correct 223 ms 356 KB Output is correct
5 Correct 452 ms 352 KB Output is correct
6 Execution timed out 695 ms 344 KB Time limit exceeded

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 348 KB Output isn't correct
3 Incorrect 0 ms 436 KB Output isn't correct
4 Incorrect 2 ms 348 KB Output isn't correct
5 Incorrect 5 ms 448 KB Output isn't correct
6 Incorrect 12 ms 344 KB Output isn't correct
7 Incorrect 23 ms 448 KB Output isn't correct
8 Incorrect 245 ms 420 KB Output isn't correct
9 Incorrect 480 ms 344 KB Output isn't correct
10 Execution timed out 690 ms 420 KB Time limit exceeded