# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1011382 | AndrijaM | Beautiful row (IZhO12_beauty) | C++14 | 6 ms | 1344 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;
typedef long long ll;
const int maxn=500;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin>>n;
int x[n+1];
int b[n+1];
int t[n+1];
memset(t,0,sizeof t);
for(int i=0;i<n;i++)
{
cin>>x[i];
b[i]=__builtin_popcount(x[i]);
vector<int>v;
int num=x[i];
while(num>0)
{
int val=num%3;
num/=3;
v.push_back(val);
}
for(int idx=0;idx<v.size();idx++)
{
if(v[idx]==1)
t[i]++;
}
}
int dp[n][(1<<n)];
memset(dp,0,sizeof dp);
for(int i=0;i<n;i++)
{
for(int k=0;(1<<k)<(1<<n);k++)
{
dp[i][(1<<k)]=1;
}
}
for(int i=1;i<(1<<n);i++)
{
for(int prev=0;prev<n;prev++)
{
if(i&(1<<prev))
{
for(int bit=0;bit<n;bit++)
{
if(i&(1<<bit))
{
}
else
{
int M=i;
M|=(1<<bit);
if(b[prev]==b[bit] || t[prev]==t[bit])
dp[bit][M]+=dp[prev][i];
}
}
}
}
}
int ans=0;
for(int i=0;i<n;i++)
{
ans+=dp[i][(1<<n)-1];
}
cout<<ans<<endl;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |