oj.uz

답안 #141002

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
141002 2019-08-06T10:43:15 Z Shelby 아름다운 순열 (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

# 결과 실행 시간 메모리 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