oj.uz

Submission #867647

# Submission time Handle Problem Language Result Execution time Memory
867647 2023-10-29T04:22:52 Z sleepntsheep Beautiful row (IZhO12_beauty) C++17
0 / 100
 1400 ms 262144 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 22

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
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 2 ms 18780 KB Output is correct
8 Correct 2 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 3 ms 18780 KB Output is correct
11 Correct 14 ms 28252 KB Output is correct
12 Correct 14 ms 28248 KB Output is correct
13 Correct 57 ms 41736 KB Output is correct
14 Correct 276 ms 87576 KB Output is correct
15 Correct 261 ms 87520 KB Output is correct
16 Correct 296 ms 87632 KB Output is correct
17 Correct 296 ms 87376 KB Output is correct
18 Correct 329 ms 87376 KB Output is correct
19 Runtime error 1400 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -