Submission #708583

#	Time	Username	Problem	Language	Result	Execution time	Memory
708583		Matjaz	Beautiful row (IZhO12_beauty)	C++14	0 / 100	3070 ms	164556 KiB

beauty

#include<vector>
#include<iostream>
#include <stdlib.h> 
#include <algorithm>
#include <stack>
#include <string.h>

using namespace std;


long long dp[1<<20][20];
int N;
vector<int> a;

int ones(int x, int base){
	int ans = 0;

	while (x > 0){
		if (x % base == 1) ans++;
		x /= base;
	}
	return ans;
}

bool works(int a, int b){
	return ones(a, 2) == ones(b,2) || ones(a, 3) == ones(b, 3);
}

long long ways(int S, int last){
	if (dp[S][last] != -1) return dp[S][last];
	if (S == (1<<N) - 1) return 1;

	long long ans = 0;


	for (int i=0;i<N;i++){
		if ((S & (1<<i)) != 0) continue;
		if (works(a[last], a[i])) ans += ways(S + (1<<i), i);
	}

	return dp[S][last] = ans;
}

int main(){
	memset(dp, -1, sizeof(dp));

	cin >> N;
	a.assign(N, 0);
	for (int i=0;i<N;i++)
		cin >> a[i];


	long long total = 0;
	for (int i=0;i<N;i++) 
		total += ways(1<<i, i);

	cout << total << endl;

	return 0;
}

• Subtask 1: 0 / 100