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;
}