# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
336125 | nikatamliani | Beautiful row (IZhO12_beauty) | C++14 | 1048 ms | 164460 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;
#define ll long long
int n, a[N], binary[N], ternary[N];
ll dp[1 << N][N];
int main() {
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> a[i];
binary[i] = __builtin_popcount(a[i]);
for(int p = a[i]; p > 0; p /= 3) {
if((p % 3) == 1) {
++ternary[i];
}
}
}
for(int mask = 0; mask < (1 << n); ++mask) {
for(int i = 0; i < n; ++i) {
if(mask >> i & 1) {
int s_mask = mask ^ (1 << i);
if(s_mask == 0) {
dp[mask][i] = 1;
continue;
}
for(int j = 0; j < n; ++j) {
if(s_mask >> j & 1) {
if(ternary[i] == ternary[j] || binary[i] == binary[j]) {
dp[mask][i] += dp[s_mask][j];
}
}
}
}
}
}
ll ans = 0;
for(int i = 0; i < n; ++i) {
ans += dp[(1 << n) - 1][i];
}
cout << ans << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |