oj.uz

Submission #857594

# Submission time Handle Problem Language Result Execution time Memory
857594 2023-10-06T12:38:21 Z TAhmed33 Beautiful row (IZhO12_beauty) C++
100 / 100
 2292 ms 164572 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("popcnt")
using namespace std;
bool ok[20][20];
long long dp[20][1<<20];
int arr[20],n;
int get1(int x) {
int cnt=0;
  x=arr[x];
while (x){
cnt+=(x%3==1);
x/=3;
}
return cnt;
}
int get2(int x) {x=arr[x];
return __builtin_popcount(x);
}
long long ans (int pos, int mask) {
long long &ret=dp[pos][mask];
if (ret !=-1) return ret;
if(mask==0) return ret=1;
ret=0;
for (int j=0;j<n;j++){
if ((mask&(1<<j))&&ok[pos][j]) ret+=ans(j,mask^(1<<j));
}
return ret;
}
int main () {
memset(dp,-1,sizeof(dp));
cin>>n;
for(int i=0;i<n;i++)cin>>arr[i];
for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
if(get1(i)==get1(j)||get2(i)==get2(j)) {
ok[i][j]=ok[j][i]=1;
}
}
long long sum=0;
for(int i=0;i<n;i++)sum+=ans(i,(1<<n)-1-(1<<i));
cout<<sum;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 164444 KB Output is correct
2 Correct 18 ms 164444 KB Output is correct
3 Correct 19 ms 164444 KB Output is correct
4 Correct 19 ms 164444 KB Output is correct
5 Correct 18 ms 164444 KB Output is correct
6 Correct 19 ms 164444 KB Output is correct
7 Correct 18 ms 164444 KB Output is correct
8 Correct 19 ms 164436 KB Output is correct
9 Correct 19 ms 164440 KB Output is correct
10 Correct 18 ms 164440 KB Output is correct
11 Correct 24 ms 164444 KB Output is correct
12 Correct 23 ms 164444 KB Output is correct
13 Correct 48 ms 164440 KB Output is correct
14 Correct 254 ms 164440 KB Output is correct
15 Correct 306 ms 164572 KB Output is correct
16 Correct 207 ms 164444 KB Output is correct
17 Correct 280 ms 164568 KB Output is correct
18 Correct 176 ms 164444 KB Output is correct
19 Correct 2025 ms 164564 KB Output is correct
20 Correct 2292 ms 164568 KB Output is correct