oj.uz

Submission #867648

# Submission time Handle Problem Language Result Execution time Memory
867648 2023-10-29T04:23:17 Z sleepntsheep Beautiful row (IZhO12_beauty) C++17
100 / 100
 1518 ms 258868 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 20

int n, a[N], b3[N];
ll ans, dp[N][1<<N][2];

inline int beautiful(int i, int j) { return (__builtin_popcount(a[i]) == __builtin_popcount(a[j])) || b3[i] == b3[j]; }

int main()
{
    ShinLena;
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        for (int x = a[i]; x; b3[i] += (x % 3) == 1, x /= 3);
        dp[i][1<<i][1] = 1;
    }
    for (int k = 0; k < (1 << n); ++k)
    {
        for (int j = 0; j < n; ++j)
        {
            if (!(k&(1<<j))) continue;
            if (dp[j][k][0]) continue;
            for (int l = 0; l < n; ++l)
            {
                if (k & (1 << l))
                {
                    if (beautiful(j, l)) dp[j][k][1] += dp[l][k&~(1<<j)][1];
                    else dp[j][k][0] += dp[l][k&~(1<<j)][1];
                }
            }
        }
    }

    for (int i = 0; i < n; ++i) ans += dp[i][(1<<n)-1][1];
    cout << ans;

    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 3 ms 18780 KB Output is correct
7 Correct 3 ms 18780 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 3 ms 18776 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 14 ms 28252 KB Output is correct
12 Correct 13 ms 28252 KB Output is correct
13 Correct 54 ms 41500 KB Output is correct
14 Correct 277 ms 87624 KB Output is correct
15 Correct 263 ms 87480 KB Output is correct
16 Correct 291 ms 87484 KB Output is correct
17 Correct 334 ms 87436 KB Output is correct
18 Correct 299 ms 87588 KB Output is correct
19 Correct 1518 ms 258868 KB Output is correct
20 Correct 1357 ms 258652 KB Output is correct