oj.uz

Submission #531032

# Submission time Handle Problem Language Result Execution time Memory
531032 2022-02-27T12:19:25 Z Homichki Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 87664 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll dp[1<<20+1][21];
ll st3(ll x)
{
    ll kol=0;
    while(x>0)
    {
        if(x%3==1)
        {
            kol++;
        }
        x/=3;
    }
    return kol;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //ifstream cin("b.in");
    //ofstream cout("b.out");
    ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
    vector<ll> a,b,st(21);
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        a.push_back(x);
    }
    st[0]=1;
    for(i=1;i<21;i++)
    {
        st[i]=st[i-1]*2;
    }
    for(i=0;i<n;i++)
    {
        dp[st[i]][i]=1;
    }
    for(mask=1;mask<st[n];mask++)
    {
        y=__builtin_popcount(mask);
        if(y>1)
        {
            for(j=0;j<n;j++)
            {
                y=mask&st[j];
                if(y>0)
                {
                    for(q=0;q<n;q++)
                    {
                        x=mask&st[q];
                        if((x>0) && (q!=j))
                        {
                            z=__builtin_popcount(a[q]);
                            y=st3(a[q]);
                            z1=__builtin_popcount(a[j]);
                            y1=st3(a[j]);
                            if((y1==y) || (z==z1))
                            {
                                dp[mask][j]+=dp[mask-st[j]][q];
                            }
                        }
                    }
                }
            }
        }
    }
    sum=0;
    for(i=0;i<n;i++)
    {
        sum+=dp[st[n]-1][i];
    }
    cout<<sum;
    return 0;
}

Compilation message

beauty.cpp:5:12: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
    5 | ll dp[1<<20+1][21];
      |          ~~^~
beauty.cpp: In function 'int main()':
beauty.cpp:25:8: warning: unused variable 'ma' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |        ^~
beauty.cpp:25:11: warning: unused variable 'qqq' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |           ^~~
beauty.cpp:25:17: warning: unused variable 'kot' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                 ^~~
beauty.cpp:25:23: warning: unused variable 'l' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                       ^
beauty.cpp:25:25: warning: unused variable 'r' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                         ^
beauty.cpp:25:29: warning: unused variable 'kry' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                             ^~~
beauty.cpp:25:33: warning: unused variable 'w' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                 ^
beauty.cpp:25:35: warning: unused variable 't' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                   ^
beauty.cpp:25:37: warning: unused variable 'm' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                     ^
beauty.cpp:25:39: warning: unused variable 'k' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                       ^
beauty.cpp:25:41: warning: unused variable 'p' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                         ^
beauty.cpp:25:43: warning: unused variable 'mi' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                           ^~
beauty.cpp:25:52: warning: unused variable 's' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                                    ^
beauty.cpp:25:58: warning: unused variable 'kol' [-Wunused-variable]
   25 |     ll ma,qqq,i,kot,j,l,r,z,kry,w,t,m,k,p,mi,x,y,n,s,sum,kol,q,mask,y1,z1;
      |                                                          ^~~

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 284 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 3 ms 460 KB Output is correct
11 Correct 61 ms 2908 KB Output is correct
12 Correct 65 ms 2960 KB Output is correct
13 Correct 323 ms 11064 KB Output is correct
14 Correct 1671 ms 43296 KB Output is correct
15 Correct 1634 ms 43376 KB Output is correct
16 Correct 1478 ms 43288 KB Output is correct
17 Correct 1452 ms 43308 KB Output is correct
18 Correct 1472 ms 43292 KB Output is correct
19 Execution timed out 3096 ms 87664 KB Time limit exceeded
20 Halted 0 ms 0 KB -