AtCoder Beginner Contest 142 E - Get Everything

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define ull unsigned long long
 5 #define pb push_back
 6 const int maxn=2e5+10;
 7 const int mod=1e9+7;
 8 int a[maxn];
 9 int c[maxn];
10 int dp[1005][(1<<12)+5];
11 
12 int main()
13 {
14     ios::sync_with_stdio(false);
15     cin.tie(0);
16     int n,m;
17     cin>>n>>m;
18     for(int i=1;i<=m;i++)
19     {
20         int x;
21         cin>>a[i]>>x;
22         int temp=0;
23         for(int j=1;j<=x;j++)
24         {
25             int y;
26             cin>>y;
27             y=1<<(y-1);
28             temp|=y;
29         }
30         c[i]=temp;
31     }
32     for(int i=0;i<=m;i++)
33     {
34         for(int j=0;j<(1<<n);j++)
35         {
36             dp[i][j]=1e9;
37         }
38     }
39     dp[0][0]=0;
40     for(int i=1;i<=m;i++)
41     {
42         for(int j=0;j<(1<<n);j++)
43         {
44             dp[i][j]=min(dp[i][j],dp[i-1][j]);
45             int k=j|c[i];
46             dp[i][k]=min(dp[i][k],dp[i-1][j]+a[i]);
47         }
48     }
49     if(dp[m][(1<<n)-1]==1e9)
50         cout<<-1<<‘\n‘;
51     else
52         cout<<dp[m][(1<<n)-1]<<‘\n‘;
53 
54 
55 }