oj.uz

Submission #93489

# Submission time Handle Problem Language Result Execution time Memory
93489 2019-01-08T18:48:08 Z zubec Beautiful row (IZhO12_beauty) C++14
100 / 100
 830 ms 127352 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 564 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 9 ms 2040 KB Output is correct
12 Correct 9 ms 2040 KB Output is correct
13 Correct 37 ms 7420 KB Output is correct
14 Correct 173 ms 30096 KB Output is correct
15 Correct 164 ms 30096 KB Output is correct
16 Correct 176 ms 30072 KB Output is correct
17 Correct 185 ms 30072 KB Output is correct
18 Correct 184 ms 30044 KB Output is correct
19 Correct 830 ms 127116 KB Output is correct
20 Correct 730 ms 127352 KB Output is correct