| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 857207 | Mohamed_Kachef06 | Beautiful row (IZhO12_beauty) | C++17 | 0 ms | 0 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;
#define int long long
#define A first
#define B second
bool comp[20][20];
int dp[20][21][1<<20];
int arr[20];
int n;
int brute(int i , int last , int mask){
if (mask == (1<<n)-1) return 1;
else if (i == n) return 0;
// if (~dp[i][last][mask]) return dp[i][last][mask];
int ans = 0;
for (int j = 0 ; j < n ; j++){
if (!(mask & (1<<j)) && (comp[last][j] || last == 20)) ans+=brute(i+1 , j , (mask | (1<<j)));
}
return dp[i][last][mask] = ans;
}
int co(int x , int b){
int a = 0;
x = arr[x];
while(x > 0){
if (x%b == 1) a++;
x/=b;
}
return a;
}
void doWork(){
cin >> n;
memset(dp , -1 , sizeof dp);
for (int i = 0 ; i < n ; i++) cin >> arr[i];
for (int i = 0 ; i < n ; i++){
for (int j = 0 ; j < n ; j++){
if (co(i , 2) == co(j , 2) || co(i , 2) == co(j , 3) || co(i , 3) == co(j , 3) || co(i , 3) == co(j , 2)) {
comp[i][j] = 1;
}
}
}
cout << brute(0 , 20 , 0);
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
doWork();
}