oj.uz

Submission #41235

# Submission time Handle Problem Language Result Execution time Memory
41235 2018-02-14T23:40:50 Z IvanC Beautiful row (IZhO12_beauty) C++14
100 / 100
 2905 ms 164708 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 20;
const int MAXL = (1 << 20);
ll dp[MAXN][MAXL];
int adj[MAXN],qtd[MAXN][2],alvo,n;
ll solve(int pos,int bitmask){
	if(bitmask == alvo){
		return 1;
	}
	if(dp[pos][bitmask] != -1) return dp[pos][bitmask];
	ll tot = 0;
	for(int nxt = 0;nxt<n;nxt++){
		if(((1 << nxt) & adj[pos]) && !((1 << nxt) & bitmask) ){
			tot += solve(nxt, (bitmask) | (1 << nxt) );
		}
	}
	return dp[pos][bitmask] = tot;
}
int main(){
	cin >> n;
	alvo = (1 << n) - 1;
	for(int i = 0;i<n;i++) memset(dp[i],-1,sizeof(dp[i]));
	for(int i = 0;i<n;i++){
		int x;
		cin >> x;
		int copia = x;
		int copia2 = x;
		for(int vez = 0;vez<31;vez++){
			if(copia % 2 == 1) qtd[i][0]++;
			copia /= 2;
			if(copia2 % 3 == 1) qtd[i][1]++;
			copia2 /= 3;
		}
		for(int j = 0;j<i;j++){
			if(qtd[i][0] == qtd[j][0]){
				adj[j] |= (1 << i);
				adj[i] |= (1 << j);
			}
			if(qtd[i][1] == qtd[j][1]){
				adj[j] |= (1 << i);
				adj[i] |= (1 << j);
			}
		}
	}
	ll tot = 0;
	for(int i = 0;i<n;i++) tot += solve(i,(1<<i));
	cout << tot << endl;
	return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16716 KB Output is correct
2 Correct 18 ms 25056 KB Output is correct
3 Correct 23 ms 33200 KB Output is correct
4 Correct 25 ms 33260 KB Output is correct
5 Correct 26 ms 33296 KB Output is correct
6 Correct 58 ms 82576 KB Output is correct
7 Correct 60 ms 82724 KB Output is correct
8 Correct 59 ms 82724 KB Output is correct
9 Correct 72 ms 82724 KB Output is correct
10 Correct 62 ms 82724 KB Output is correct
11 Correct 95 ms 115364 KB Output is correct
12 Correct 92 ms 115364 KB Output is correct
13 Correct 154 ms 131932 KB Output is correct
14 Correct 435 ms 148304 KB Output is correct
15 Correct 520 ms 148380 KB Output is correct
16 Correct 393 ms 148508 KB Output is correct
17 Correct 489 ms 148508 KB Output is correct
18 Correct 324 ms 148508 KB Output is correct
19 Correct 2633 ms 164676 KB Output is correct
20 Correct 2905 ms 164708 KB Output is correct