Submission #1049244

#TimeUsernameProblemLanguageResultExecution timeMemory
1049244sofija6Beautiful row (IZhO12_beauty)C++14
100 / 100
578 ms172788 KiB
#include <bits/stdc++.h> #define ll long long #define MAXN 21 using namespace std; ll a[MAXN],dp[1<<MAXN][MAXN]; bool ok[MAXN][MAXN]; ll Count(ll x) { ll cur=387420489ll,cnt=0; while (x) { if (x/cur==1) cnt++; x%=cur; cur/=3; } return cnt; } bool Check(ll x,ll y) { if (__builtin_popcount(x)==__builtin_popcount(y)) return true; if (Count(x)==Count(y)) return true; return false; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n; cin >> n; for (ll i=0;i<n;i++) { cin >> a[i]; dp[1<<i][i]=1; } for (ll i=0;i<n;i++) { for (ll j=0;j<n;j++) ok[i][j]=Check(a[i],a[j]); } for (ll i=1;i<(1<<n);i++) { for (ll j=0;j<n;j++) { if (!((1<<j)&i)) continue; for (ll k=0;k<n;k++) { if ((1<<k)&i || !ok[j][k]) continue; dp[i|(1<<k)][k]+=dp[i][j]; } } } ll ans=0; for (ll i=0;i<n;i++) ans+=dp[(1<<n)-1][i]; cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...