Submission #531033

#	Time	Username	Problem	Language	Result	Execution time	Memory
531033		Homichki	Beautiful row (IZhO12_beauty)	C++17	100 / 100	972 ms	172668 KiB

beauty

#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);
    vector<pair<ll,ll> > mo;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>x;
        a.push_back(x);
        z1=__builtin_popcount(x);
        y1=st3(x);
        mo.push_back({z1,y1});
    }
    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))
                        {
                            if((mo[j].first==mo[q].first) || (mo[j].second==mo[q].second))
                            {
                                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 (stderr)

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:27: warning: unused variable 'z' [-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: 100 / 100