oj.uz

Submission #867646

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

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 2392 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 3 ms 18780 KB Output is correct
9 Correct 3 ms 18780 KB Output is correct
10 Correct 3 ms 18776 KB Output is correct
11 Correct 15 ms 28504 KB Output is correct
12 Correct 13 ms 28252 KB Output is correct
13 Correct 54 ms 41652 KB Output is correct
14 Correct 282 ms 87444 KB Output is correct
15 Correct 308 ms 87628 KB Output is correct
16 Correct 290 ms 87380 KB Output is correct
17 Correct 295 ms 87380 KB Output is correct
18 Correct 325 ms 87440 KB Output is correct
19 Runtime error 1376 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -