oj.uz

Submission #141002

# Submission time Handle Problem Language Result Execution time Memory
141002 2019-08-06T10:43:15 Z Shelby Beautiful row (IZhO12_beauty) C++11
100 / 100
 1037 ms 164632 KB 
#include <bits/stdc++.h>

using namespace std;

long long dp[1<<20][20];
int t[20],b[20],a[20];
bool v[20][20];

int main()
{ int n,i,j,x,tmp,mask;
long long sol=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
    scanf("%d",&a[i]);

    b[i]=__builtin_popcount(a[i]);

    x=a[i];

    while(x>0)
    {
        tmp=x%3;

        if(tmp==1) t[i]++;

        x=x/3;
    }
}

for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        if((b[i]==b[j] || t[i]==t[j]) && (i!=j)) v[i][j]=true;
    }
}

for(i=0;i<n;i++) dp[(1<<i)][i]=1;


for(mask=1;mask<(1<<n);mask++)
{
    for(i=0;i<n;i++)
    {
        if(mask&(1<<i))
        {
            for(j=0;j<n;j++)
            {
                if( (mask&(1<<j))==0 && v[i][j]==true )
                {
                    dp[mask|(1<<j)][j]+=dp[mask][i];
                }
            }
        }
    }
}

for(i=0;i<n;i++) sol+=dp[(1<<n)-1][i];

printf("%lld\n",sol);

    return 0;
}

Compilation message

beauty.cpp: In function 'int main()':
beauty.cpp:12:6: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 scanf("%d",&n);
 ~~~~~^~~~~~~~~
beauty.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&a[i]);
     ~~~~~^~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 12 ms 3064 KB Output is correct
12 Correct 11 ms 2936 KB Output is correct
13 Correct 44 ms 10620 KB Output is correct
14 Correct 214 ms 41336 KB Output is correct
15 Correct 200 ms 41416 KB Output is correct
16 Correct 218 ms 41368 KB Output is correct
17 Correct 221 ms 41352 KB Output is correct
18 Correct 254 ms 41560 KB Output is correct
19 Correct 1037 ms 164632 KB Output is correct
20 Correct 913 ms 164568 KB Output is correct