Submission #41235

#TimeUsernameProblemLanguageResultExecution timeMemory
41235IvanCBeautiful row (IZhO12_beauty)C++14
100 / 100
2905 ms164708 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 20; const int MAXL = (1 << 20); ll dp[MAXN][MAXL]; int adj[MAXN],qtd[MAXN][2],alvo,n; ll solve(int pos,int bitmask){ if(bitmask == alvo){ return 1; } if(dp[pos][bitmask] != -1) return dp[pos][bitmask]; ll tot = 0; for(int nxt = 0;nxt<n;nxt++){ if(((1 << nxt) & adj[pos]) && !((1 << nxt) & bitmask) ){ tot += solve(nxt, (bitmask) | (1 << nxt) ); } } return dp[pos][bitmask] = tot; } int main(){ cin >> n; alvo = (1 << n) - 1; for(int i = 0;i<n;i++) memset(dp[i],-1,sizeof(dp[i])); for(int i = 0;i<n;i++){ int x; cin >> x; int copia = x; int copia2 = x; for(int vez = 0;vez<31;vez++){ if(copia % 2 == 1) qtd[i][0]++; copia /= 2; if(copia2 % 3 == 1) qtd[i][1]++; copia2 /= 3; } for(int j = 0;j<i;j++){ if(qtd[i][0] == qtd[j][0]){ adj[j] |= (1 << i); adj[i] |= (1 << j); } if(qtd[i][1] == qtd[j][1]){ adj[j] |= (1 << i); adj[i] |= (1 << j); } } } ll tot = 0; for(int i = 0;i<n;i++) tot += solve(i,(1<<i)); cout << tot << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...