C++(g++ 7.5.0) 解法, 执行用时: 568ms, 内存消耗: 1472K, 提交时间: 2022-09-09 23:32:35

// Nothing is Given, Everything is Earned.
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int main()
{
	cin.tie(NULL)->sync_with_stdio(false);
	int n,k,m; cin>>n>>k>>m;
	vector<pair<int, int>> a(n);
	for(int i=0,q;i<n;i++)
	{
		cin>>a[i].X>>q;
		while(q--)
		{
			int c; cin>>c; c--;
			a[i].Y|=1<<c;
		}
	}
	sort(a.begin(),a.end());
	vector<int> popcnt(1<<m);
	for(int i=0;i<1<<m;i++) popcnt[i]=__builtin_popcount(i);
	vector<int> suf(n+1),sum(n+1);
	for(int i=n-1;~i;i--)
	{
		suf[i]=suf[i+1]|a[i].Y;
		sum[i]=sum[i+1]+a[i].X;
	}
	vector f(m+1,vector(1<<m,-1));
	for(int i=0;i<=min(m,k);i++) f[i][0]=0;
	int ans=0;
	for(int i=n-1;~i;i--)
	{
		vector g(m+1,vector(1<<m,-1));
		for(int j=0;j<=m;j++)
		{
			for(int S=0;S<1<<m;S++) if(~f[j][S])
			{
				if(j) g[j-1][S|a[i].Y]=max(g[j-1][S|a[i].Y],f[j][S]);
				g[j][S]=max(g[j][S],f[j][S]+(j+n-i-1<k?a[i].X:0));
			}
		}
		swap(f,g);
		for(int S=0;S<1<<m;S++) ans=max(ans,popcnt[S]*f[0][S]);
	}
	cout<<ans<<"\n";
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 997ms, 内存消耗: 2296K, 提交时间: 2022-09-10 11:21:09

#include<bits/stdc++.h>
using namespace std;
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define mod 998244353
#define N 1005
#define M 13
int n,m,K;
ll f[M+1][1<<M],g[M+1][1<<M],ans;
void chmx(ll& x,ll y){
	if(x<y)x=y;
}
struct node{
	int x,y;
	friend bool operator< (node A,node B){
		return A.x>B.x;
	}
}a[N];
int main(){
	scanf("%d%d%d",&n,&K,&m);
	fr(i,1,n){
		int len,z;
		scanf("%d%d",&a[i].x,&len);
		fr(j,1,len){
			scanf("%d",&z);
			a[i].y|=(1<<(z-1));
		}
	}
	sort(a+1,a+n+1);
	memset(f,-0x3f,sizeof f);
	fr(i,0,m)f[i][0]=0;
	fr(i,1,n){
		int x=a[i].x,y=a[i].y;
		memcpy(g,f,sizeof f);
		fr(k,0,(1<<m)-1){
			fr(j,0,m){
				if(j)chmx(g[j-1][k|y],f[j][k]);
				if(j+i<=K)chmx(g[j][k],f[j][k]+x);
			}
		}
		memcpy(f,g,sizeof f);
	}
	fr(k,0,(1<<m)-1)if(f[0][k]>0)chmx(ans,f[0][k]*__builtin_popcount(k));
	printf("%lld\n",ans);
    return 0;
}