oj.uz

Submission #638858

# Submission time Handle Problem Language Result Execution time Memory
638858 2022-09-07T17:35:23 Z MohamedAhmed04 Beautiful row (IZhO12_beauty) C++14
100 / 100
 870 ms 127560 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 8 ms 1896 KB Output is correct
12 Correct 7 ms 2004 KB Output is correct
13 Correct 36 ms 7316 KB Output is correct
14 Correct 176 ms 30200 KB Output is correct
15 Correct 157 ms 30156 KB Output is correct
16 Correct 167 ms 30060 KB Output is correct
17 Correct 221 ms 30084 KB Output is correct
18 Correct 174 ms 30048 KB Output is correct
19 Correct 836 ms 127560 KB Output is correct
20 Correct 870 ms 127488 KB Output is correct