oj.uz

Submission #339835

# Submission time Handle Problem Language Result Execution time Memory
339835 2020-12-26T09:34:48 Z nandonathaniel Beautiful row (IZhO12_beauty) C++14
0 / 100
 3000 ms 164664 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=20;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC option("arch=native","tune=native","no-zero-upper")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
int n;
long long dp[1<<MAXN][MAXN];
int a[MAXN];

int binary(int x){
	return __builtin_popcount(x);
}

int ternary(int x){
	int ret=0;
	while(x>0){
		if(x%3==1)ret++;
		x/=3;
	}
	return ret;
}

long long DP(int mask,int last){
	if(mask==((1<<n)-1))return 1;
	long long &ret=dp[mask][last];
	if(ret!=-1)return ret;
	ret=0;
	for(int i=0;i<n;i++){
		if(!(mask & (1<<i))){
			if(binary(a[last])==binary(a[i]) || ternary(a[last])==ternary(a[i]))ret+=DP(mask+(1<<i),i);
		}
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i=0;i<n;i++)cin >> a[i];
	memset(dp,-1,sizeof(dp));
	long long ans=0;
	for(int i=0;i<n;i++)ans+=DP(1<<i,i);
	cout << ans << '\n';
	return 0;
}

Compilation message

beauty.cpp:5: warning: ignoring #pragma GCC option [-Wunknown-pragmas]
    5 | #pragma GCC option("arch=native","tune=native","no-zero-upper")
      |

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 164460 KB Output is correct
2 Correct 80 ms 164460 KB Output is correct
3 Correct 92 ms 164460 KB Output is correct
4 Correct 82 ms 164460 KB Output is correct
5 Correct 81 ms 164460 KB Output is correct
6 Correct 80 ms 164460 KB Output is correct
7 Correct 80 ms 164588 KB Output is correct
8 Correct 85 ms 164460 KB Output is correct
9 Correct 82 ms 164460 KB Output is correct
10 Correct 91 ms 164460 KB Output is correct
11 Correct 96 ms 164460 KB Output is correct
12 Correct 94 ms 164460 KB Output is correct
13 Correct 187 ms 164588 KB Output is correct
14 Correct 793 ms 164588 KB Output is correct
15 Correct 624 ms 164460 KB Output is correct
16 Correct 886 ms 164664 KB Output is correct
17 Correct 912 ms 164548 KB Output is correct
18 Correct 707 ms 164460 KB Output is correct
19 Execution timed out 3063 ms 164460 KB Time limit exceeded
20 Halted 0 ms 0 KB -