oj.uz

Submission #531033

# Submission time Handle Problem Language Result Execution time Memory
531033 2022-02-27T12:23:56 Z Homichki Beautiful row (IZhO12_beauty) C++17
100 / 100
 972 ms 172668 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);
    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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 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 1 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 1 ms 460 KB Output is correct
11 Correct 10 ms 2944 KB Output is correct
12 Correct 10 ms 2972 KB Output is correct
13 Correct 41 ms 11080 KB Output is correct
14 Correct 195 ms 43276 KB Output is correct
15 Correct 203 ms 43356 KB Output is correct
16 Correct 201 ms 43336 KB Output is correct
17 Correct 214 ms 43392 KB Output is correct
18 Correct 210 ms 43324 KB Output is correct
19 Correct 972 ms 172584 KB Output is correct
20 Correct 842 ms 172668 KB Output is correct