oj.uz

Submission #531028

# Submission time Handle Problem Language Result Execution time Memory
531028 2022-02-27T12:13:04 Z Homichki Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 89868 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("longpath.in");
    //ofstream cout("longpath.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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 1 ms 284 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 448 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 2 ms 444 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 60 ms 2884 KB Output is correct
12 Correct 64 ms 3108 KB Output is correct
13 Correct 309 ms 11064 KB Output is correct
14 Correct 1532 ms 43468 KB Output is correct
15 Correct 1569 ms 43372 KB Output is correct
16 Correct 1453 ms 43492 KB Output is correct
17 Correct 1398 ms 43424 KB Output is correct
18 Correct 1443 ms 43444 KB Output is correct
19 Execution timed out 3066 ms 89868 KB Time limit exceeded
20 Halted 0 ms 0 KB -