记录编号	245606	评测结果	AAAAAAAAAA
题目名称	[USACO Open05] 疾病管理	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.491 s
提交时间	2016-04-03 21:04:54	内存使用	0.51 MiB

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
using namespace std;

int fast_read_int()
{
	char ch;
	int ret;
	while(ch = getchar())
	{
		if(ch >= '0' && ch <= '9')
		{
			ret = ch ^ 0x30;
			break;
		}
	}
	while(isdigit(ch = getchar()))ret = (ret << 3)+(ret << 1)+(ch^'0');
	return ret;
}
#define MAXN 1001
int cow[MAXN];
int dp[1<<16];

#define GAINILL(n) (1<<(n-1))

inline bool ok(int s, int d, int k)
{
	int c = 0;
	for(int i = 1; i <= d; i++)
	{
		if(GAINILL(i)&s)
		{
			c++;
			if(c > k)return false;
		}
	}
	return true;
}

int main()
{
	freopen("disease.in", "r", stdin);
	freopen("disease.out", "w", stdout);
	int n,d,k;
	int r = 0;
	n = fast_read_int();
	d = fast_read_int();
	k = fast_read_int();
	for(int i = 1; i <= n; i++)
	{
		int m = fast_read_int();
		while(m--)
		{
			int l = fast_read_int();
			cow[i] |= GAINILL(l);
		}
	}
	for(int i = 1; i <= n; i++)
		for(int j = (1<<d)-1; j >= 0; j--)
			dp[j|cow[i]] = max(dp[j|cow[i]], dp[j] + 1);
	for(int i = 0; i <= (1<<d)-1; i++)
		if(ok(i, d, k))r = max(r, dp[i]);
	printf("%d\n", r);
	return 0;
}