Submission #90169

#TimeUsernameProblemLanguageResultExecution timeMemory
90169popovicirobertBeautiful row (IZhO12_beauty)C++14
100 / 100
725 ms164892 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long #define ld long double // 217 // 44 using namespace std; const int MAXN = 20; ll dp[1 << MAXN][MAXN]; int cnt2[MAXN], cnt3[MAXN]; inline int get2(int x) { return __builtin_popcount(x); } inline int get3(int x) { int cnt = 0; while(x > 0) { cnt += ((x % 3) == 1); x /= 3; } return cnt; } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n; for(i = 0; i < n; i++) { int x; cin >> x; cnt2[i] = get2(x); cnt3[i] = get3(x); } for(int conf = 1; conf < (1 << n); conf++) { if((conf & (conf - 1)) == 0) { int bit = 0; while((conf & (1 << bit)) == 0) { bit++; } dp[conf][bit] = 1; } else { vector <int> cur; for(int bit = 0; bit < n; bit++) { if(conf & (1 << bit)) { cur.push_back(bit); } } int sz = cur.size(); for(int a = 0; a < sz; a++) { for(int b = 0; b < sz; b++) { if(a != b && (cnt2[cur[a]] == cnt2[cur[b]] || cnt3[cur[a]] == cnt3[cur[b]])) { dp[conf][cur[a]] += dp[conf ^ (1 << cur[a])][cur[b]]; } } } } } ll ans = 0; for(i = 0; i < n; i++) { ans += dp[(1 << n) - 1][i]; } cout << ans; //cin.close(); //cout.close(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...