oj.uz

Submission #4810

# Submission time Handle Problem Language Result Execution time Memory
4810 2014-01-04T11:23:10 Z cki86201 Beautiful row (IZhO12_beauty) C++
100 / 100
 1136 ms 164928 KB 
#include<stdio.h>

typedef long long ll;
ll dp[1<<20][20],ans;
int inp[22],n;
bool chk[22][22];
int data[2][22];

int count1(int x,int y)
{
	int ret = 0;
	while(x){
		ret += (x%y==1);
		x/=y;
	}
	return ret;
}

int main(){
	scanf("%d",&n);
	int i;
	for(i=0;i<n;i++)scanf("%d",inp+i);
	for(i=0;i<n;i++)data[0][i] = count1(inp[i],2), data[1][i] = count1(inp[i],3);
	for(i=0;i<n;i++)for(int j=0;j<n;j++)chk[i][j] = (data[0][i]==data[0][j] || data[1][i]==data[1][j]);
	for(i=0;i<n;i++)dp[0][i]=1;
	for(int b=0;b<1<<n;b++){
		for(i=0;i<n;i++){
			if(b&1<<i)continue;
			for(int j=0;j<n;j++){
				if((b|1<<i) & 1<<j)continue;
				if(chk[i][j])dp[b|1<<i][j] += dp[b][i];
			}
			if((b|1<<i)+1 == 1<<n)ans += dp[b][i];
		}
	}
	printf("%lld",ans);
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 164928 KB Output is correct
2 Correct 0 ms 164928 KB Output is correct
3 Correct 0 ms 164928 KB Output is correct
4 Correct 0 ms 164928 KB Output is correct
5 Correct 0 ms 164928 KB Output is correct
6 Correct 0 ms 164928 KB Output is correct
7 Correct 0 ms 164928 KB Output is correct
8 Correct 0 ms 164928 KB Output is correct
9 Correct 0 ms 164928 KB Output is correct
10 Correct 0 ms 164928 KB Output is correct
11 Correct 8 ms 164928 KB Output is correct
12 Correct 8 ms 164928 KB Output is correct
13 Correct 40 ms 164928 KB Output is correct
14 Correct 212 ms 164928 KB Output is correct
15 Correct 224 ms 164928 KB Output is correct
16 Correct 228 ms 164928 KB Output is correct
17 Correct 240 ms 164928 KB Output is correct
18 Correct 236 ms 164928 KB Output is correct
19 Correct 1136 ms 164928 KB Output is correct
20 Correct 1028 ms 164928 KB Output is correct