oj.uz

Submission #857550

# Submission time Handle Problem Language Result Execution time Memory
857550 2023-10-06T11:40:16 Z Mohamed_Kachef06 Beautiful row (IZhO12_beauty) C++17
0 / 100
 3000 ms 164808 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define A first
#define B second

int n ,  a[20] , dp[20][1<<20] , co[20][20]; 

int fact(int i , int b){
    int x = a[i];
    int ans =0 ;
    while(x > 0){
        if (x%b == 1) ans++;
        x/=b;
    }
    return ans;
}

void pre(){
    for (int i = 0 ; i < n ; i++) {
        for (int j = 0 ; j < n ; j++){
            int a = fact(i ,2), b = fact(i , 3) , c = fact(j ,2 ) , d= fact(j , 3);
            if (a == c || b == d) co[i][j] = 1;
        }
    }
}

int brute(int last , int mask){
    int y = __builtin_popcountll(mask);
    if (y == n) return 1;
    if (~dp[last][mask]) return dp[last][mask];
    int ans = 0 ;
    for (int i = 0 ; i < n ; i++){
        if (!(mask & (1<<i))){
            int x = brute(i , (mask | (1<<i)));
            if (y == 0 || co[last][i]) ans += x;
        }
    }
    return dp[last][mask] =  ans;
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i = 0 ; i < n ; i++) cin >> a[i];
    memset(dp , -1 , sizeof dp);
    pre();
    cout << brute(0 , 0); 
}

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 164444 KB Output is correct
2 Correct 20 ms 164440 KB Output is correct
3 Correct 19 ms 164520 KB Output is correct
4 Correct 22 ms 164532 KB Output is correct
5 Correct 19 ms 164508 KB Output is correct
6 Correct 21 ms 164444 KB Output is correct
7 Correct 19 ms 164444 KB Output is correct
8 Correct 21 ms 164592 KB Output is correct
9 Correct 22 ms 164436 KB Output is correct
10 Correct 20 ms 164440 KB Output is correct
11 Correct 30 ms 164604 KB Output is correct
12 Correct 31 ms 164808 KB Output is correct
13 Correct 79 ms 164388 KB Output is correct
14 Correct 479 ms 164592 KB Output is correct
15 Correct 502 ms 164520 KB Output is correct
16 Correct 466 ms 164604 KB Output is correct
17 Correct 491 ms 164596 KB Output is correct
18 Correct 519 ms 164600 KB Output is correct
19 Execution timed out 3056 ms 164444 KB Time limit exceeded
20 Halted 0 ms 0 KB -