记录编号	137276	评测结果	AAAAAAAAAA
题目名称	[東方S3] 稗田阿求	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2014-11-04 16:50:26	内存使用	0.31 MiB

#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
const double lg2(log(2));
int m, f[60][26], ans;
long long ban[60];
char str[105];
set<long long> s;
inline int pc(long long x){
	x = (x >> 1 & 0x5555555555555555ll) + (x & 0x5555555555555555ll);
	x = (x >> 2 & 0x3333333333333333ll) + (x & 0x3333333333333333ll);
	x = (x >> 4 & 0x0f0f0f0f0f0f0f0fll) + (x & 0x0f0f0f0f0f0f0f0fll);
	x = (x >> 8 & 0x00ff00ff00ff00ffll) + (x & 0x00ff00ff00ff00ffll);
	x = (x >> 16 & 0x0000ffff0000ffffll) + (x & 0x0000ffff0000ffffll);
	x = (x >> 32 & 0x00000000ffffffffll) + (x & 0x00000000ffffffffll);
	return x;
}
void dfs(long long st, long long can){
	int t(pc(st));
	if (t + pc(can) <= ans) return;
	if (s.find(st) != s.end()) return;
	s.insert(st);
	if (ans < t) ans = t;
	long long now, nc(can);
	while (can){
		can -= now = can & -can;
		t = log(now) / lg2 + 0.1;
		if (ban[t] & st) continue;
		dfs(st | now, nc & ~ban[t]);
	}
}
int main(){
	freopen("akyuu.in", "r", stdin);
	freopen("akyuu.out", "w", stdout);
	int i, j, k;
	scanf("%d%d", &m, &m);
	for (i = 0; i < m; ++i){
		ban[i] = 1ll << i;
		scanf("%s", str);
		for (j = 0; str[j]; ++j){
			scanf("%d", &k);
			f[i][str[j] - 'A'] = k;
		}
		for (j = 0; j < i; ++j){
			for (k = 0; k < 26; ++k)
				if (f[i][k] && f[j][k] && f[i][k] != f[j][k]) break;
			if (k < 26) ban[i] |= 1ll << j, ban[j] |= 1ll << i;
		}
	}
	dfs(0, (1ll << m) - 1);
	printf("%d\n", ans);
	return 0;
}