oj.uz

Submission #282444

# Submission time Handle Problem Language Result Execution time Memory
282444 2020-08-24T12:29:53 Z keta_tsimakuridze Beautiful row (IZhO12_beauty) C++14
100 / 100
 980 ms 205556 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
long long n,k,b,ones[2][25],cur,a[25],dp[2000005][25],ans;
 main(){
	cin>>n;
	for(k=0;k<n;k++){
		cin>>a[k];
		b=a[k];
		while(b){
			if(b%2) ones[0][k]++;
			b/=2;
		}
		b=a[k];
		while(b){
			if(b%3==1) ones[1][k]++;
			b/=3;
		}
		dp[1<<k][k]=1;
	}
	for(k=1;k<(1<<n);k++){
		for(int j=0;j<n;j++){
			b=1ll<<j;
			if(! (b&k)) continue;
			cur=k^b;
		for(int i=0;i<n;i++){
			b=1ll<<i;
			if(!(b&cur)) continue;
		//	cout<<k<<" "<<i<<" "<<j<<endl;
			if(ones[0][j]==ones[0][i] || ones[1][j]==ones[1][i]){
			dp[k][j]+=dp[cur][i];// cout<<cur<<" "<<i<<endl;
			
		} }
	//	cout<<k<<"_"<<j<<" "<<dp[k][j]<<endl;
		if(k == ((1<<n) -1)) ans+=dp[k][j];
	} }
	cout<<ans;
}

Compilation message

beauty.cpp:5:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    5 |  main(){
      |       ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 288 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 512 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 512 KB Output is correct
11 Correct 12 ms 3584 KB Output is correct
12 Correct 12 ms 3584 KB Output is correct
13 Correct 47 ms 13176 KB Output is correct
14 Correct 208 ms 51640 KB Output is correct
15 Correct 184 ms 51576 KB Output is correct
16 Correct 210 ms 51696 KB Output is correct
17 Correct 228 ms 51832 KB Output is correct
18 Correct 216 ms 51608 KB Output is correct
19 Correct 980 ms 205556 KB Output is correct
20 Correct 826 ms 205468 KB Output is correct