Submission #638858

#	Time	Username	Problem	Language	Result	Execution time	Memory
638858		MohamedAhmed04	Beautiful row (IZhO12_beauty)	C++14	100 / 100	870 ms	127560 KiB

beauty

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 20 ;

int arr[MAX] ;
int n ;

int cnt2[MAX] , cnt3[MAX] ;

int calc(int x)
{
	int cnt = 0 ;
	while(x > 0)
	{
		cnt += (x%3 == 1) ;
		x /= 3 ;
	}
	return cnt ;
}

long long dp[MAX][(1 << MAX)] ;

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n ;
	for(int i = 0 ; i < n ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < n ; ++i)
		cnt2[i] = __builtin_popcount(arr[i]) , cnt3[i] = calc(arr[i]) ;
	for(int i = 0 ; i < n ; ++i)
		dp[i][(1 << i)] = 1 ;
	for(int mask = 0 ; mask < (1 << n) ; ++mask)
	{
		for(int i = 0 ; i < n ; ++i)
		{
			if((!(mask & (1 << i))))
				continue ;
			for(int j = 0 ; j < n ; ++j)
			{
				if((!(mask & (1 << j))))
					continue ;
				if(cnt2[i] == cnt2[j] || cnt3[i] == cnt3[j])
					dp[i][mask] += dp[j][mask ^ (1 << i)] ;
			}
		}
	}
	long long ans = 0 ;
	for(int i = 0 ; i < n ; ++i)
		ans += dp[i][(1 << n) - 1] ;
	return cout<<ans<<"\n" , 0 ;
}		

• Subtask 1: 100 / 100