Submission #339664

#TimeUsernameProblemLanguageResultExecution timeMemory
339664Ahmad_HasanBeautiful row (IZhO12_beauty)C++17
0 / 100
3102 ms205548 KiB
#include <bits/stdc++.h> #define int long long using namespace std; int n; vector<int> nums; int cnt=0ll; vector<vector<int> > dp; vector<int>b2,b3; int slv(int msk=0,int lstidx=-1){ if(msk==(1ll<<n)-1ll){ return 1ll; } int cnt=0; if(lstidx!=-1&&dp[msk][lstidx]!=-1) return dp[msk][lstidx]; for(int i=0;i<n;i++){ if(!(msk&(1<<i))){ if(lstidx==-1){ cnt+=slv(msk|(1ll<<i),i); continue; } int f=(b2[i]==b2[lstidx])||(b3[i]==b3[lstidx]); if(f){ cnt+=slv(msk|(1ll<<i),i); } } } if(lstidx!=-1) dp[msk][lstidx]=cnt; return cnt; } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; nums=vector<int>(n); for(int i=0;i<n;i++){ cin>>nums[i]; } dp=vector<vector<int> >((1<<n),vector<int>(n,-1ll)); b2=b3=vector<int>(n); for(int i=0;i<n;i++){ int cntb2=0; int num1=nums[i]; while(num1){ cntb2+=num1%2ll; num1/=2ll; } b2[i]=cntb2; int cntb3=0; num1=nums[i]; while(num1){ cntb3+=(num1%3ll==1ll); num1/=3ll; } b3[i]=cntb3; } cout<<(long long)slv(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...