oj.uz

Submission #479848

# Submission time Handle Problem Language Result Execution time Memory
479848 2021-10-13T13:51:46 Z hjc4vr Beautiful row (IZhO12_beauty) C++14
100 / 100
 1025 ms 172748 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
int const maxn = 2005,MOD=1e9 + 7;
int d[maxn];
struct road{
    int a,b,cost;
};

int pow(int a,int b){
    int result = 1;
    while (b>0){
        if (b&1) {
            result *= a;
        }
        a = a*a;
        b = b>>1;
    }
    return result;
}
int gcd(int a,int b){
    if (b==0) return a;
    if (a<b) swap(a,b);
    return gcd(b,a%b);
}
int count2(int x){
    return __builtin_popcount(x);
}
int count3(int x){
    int cnt=0;
    while (x){
        if (x%3==1) cnt++;
        x/=3;
    }
    return cnt;
}
int dp[1<<20][21];
void solve(){
    int n;cin>>n;
    int arr[n+1];
    for (int i=1;i<=n;++i) cin >> arr[i];
    pair<int,int> v[n+1];
    for (int i=1;i<=n;++i) v[i] = make_pair(count2(arr[i]),count3(arr[i]));
    for (int mask=1;mask<(1<<n);++mask){
        int sz=0;
        int last=0;
        for (int i=0;i<n;++i) if ((1<<i)&mask) sz++, last = i;
        if (sz==1) dp[mask][last] = 1;
        else{
            for (int i=0;i<n;++i){
                if ((1<<i)&mask){
                    int next_mask = (1<<i)^mask;
                    for (int j=0;j<n;++j){
                        if ((1<<j)&next_mask and (v[j+1].first==v[i+1].first or v[j+1].second==v[i+1].second)){
                            dp[mask][i] += dp[next_mask][j];
                        }
                    }
                }
            }
        }
    }
    int ans =0;
    for (int i=0;i<n;++i) ans += dp[(1<<n)-1][i];
    cout << ans;
}
int32_t main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    solve();
}
   
//
//4
//4
//2
//2
//2
//4
//4
//4
//4
//2
//4
//4
//2

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 10 ms 2960 KB Output is correct
12 Correct 12 ms 2892 KB Output is correct
13 Correct 47 ms 10968 KB Output is correct
14 Correct 208 ms 43396 KB Output is correct
15 Correct 191 ms 43504 KB Output is correct
16 Correct 220 ms 43388 KB Output is correct
17 Correct 227 ms 43372 KB Output is correct
18 Correct 253 ms 43304 KB Output is correct
19 Correct 1025 ms 172748 KB Output is correct
20 Correct 835 ms 172608 KB Output is correct