Submission #93489

#	Time	Username	Problem	Language	Result	Execution time	Memory
93489		zubec	Beautiful row (IZhO12_beauty)	C++14	100 / 100	830 ms	127352 KiB

beauty

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;


ll dp[25][(1<<20)+5];

pair<int, int> a[25];

int n;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("beautiful.in", "r", stdin);freopen("beautiful.out", "w", stdout);

    cin >> n;
    for (int i = 0; i < n; i++){
        int x;
        cin >> x;
        int ncp = x;
        while(ncp){
            a[i].first += (ncp % 2 == 1);
            ncp /= 2;
        }
        ncp = x;
        while(ncp){
            a[i].second += (ncp % 3 == 1);
            ncp /= 3;
        }
        dp[i][(1<<i)] = 1;
        //cout << i << ' ' << a[i].first << ' ' << a[i].second << endl;
    }
    for (int mask = 1; mask < (1<<n); mask++){
        for (int i = 0; i < n; i++){
            if (!(mask & (1<<i)))
                continue;
            for (int j = 0; j < n; j++){
                if (mask & (1<<j))
                    continue;
                if (!(a[i].first == a[j].first || a[i].second == a[j].second))
                    continue;
                dp[j][mask|(1<<j)] += dp[i][mask];
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < n; i++)
        ans += dp[i][(1<<n)-1];

    cout << ans;

}

• Subtask 1: 100 / 100