제출 #708589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
708589		Matjaz	Beautiful row (IZhO12_beauty)	C++14	100 / 100	2705 ms	164528 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 onesdp[20][4];

int ones(int x, int base){
	if (onesdp[x][base] != -1) return onesdp[x][base];
	int ans = 0;

	int tmp = a[x];

	while (tmp > 0){
		if (tmp % base == 1) ans++;
		tmp /= base;
	}
	return onesdp[x][base] = 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(last, i)) ans += ways(S + (1<<i), i);
	}

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

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

	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: 100 / 100