# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1037018 | pera | Beautiful row (IZhO12_beauty) | C++17 | 628 ms | 172892 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 20 , LOG = 30;
int n;
vector<int> a(N);
vector<vector<long long>> dp(N , vector<long long>(1 << N));
vector<vector<int>> v(N);
int t_o_c(int x){
int cnt = 0;
while(x > 0){
cnt += (x % 3 == 1);
x /= 3;
}
return cnt;
}
int main(){
cin >> n;
for(int i = 0;i < n;i ++){
cin >> a[i];
}
for(int x = 0;x < n;x ++){
for(int y = 0;y < n;y ++){
if(x != y && (__builtin_popcount(a[x]) == __builtin_popcount(a[y]) || t_o_c(a[x]) == t_o_c(a[y]))){
v[x].push_back(y);
}
}
dp[x][1 << x] = 1LL;
}
for(int mask = 0;mask < (1 << n);mask ++){
for(int x = 0;x < n;x ++){
if(mask >> x & 1){
for(int y : v[x]){
if(mask >> y & 1){
dp[x][mask] += dp[y][mask ^ (1 << x)];
}
}
}
}
}
long long ans = 0;
for(int i = 0;i < n;i ++){
ans += dp[i][(1 << n) - 1];
}
cout << ans << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |