Submission #7778025


Source Code Expand

Copy
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

const int INF=1e18;

signed main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N,M; cin>>N>>M;
    vector<int> a(M),T(M);
    for(int i=0;i<M;i++){
        int k; cin>>a[i]>>k;
        while(k--){
            int c; cin>>c;
            c--;
            T[i]|=1<<c;
        }
    }

    vector<vector<int>> dp(M+1,vector<int>(1<<N,INF));
    dp[0][0]=0;
    for(int i=0;i<M;i++){
        for(int S=0;S<(1<<N);S++){
            chmin(dp[i+1][S],dp[i][S]);
            chmin(dp[i+1][S|T[i]],dp[i][S]+a[i]);
        }
    }
    int ans=dp[M][(1<<N)-1];
    cout<<(ans==INF? -1:ans)<<endl;
    return 0;
}

Submission Info

Submission Time
Task E - Get Everything
User tekihei2317
Language C++14 (GCC 5.4.1)
Score 500
Code Size 895 Byte
Status AC
Exec Time 27 ms
Memory 32384 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 40
Set Name Test Cases
Sample 00-sample-00, 00-sample-01, 00-sample-02
All 00-sample-00, 00-sample-01, 00-sample-02, 01-handmade-03, 01-handmade-04, 01-handmade-05, 01-handmade-06, 01-handmade-07, 02-random-08, 02-random-09, 02-random-10, 02-random-11, 02-random-12, 02-random-13, 02-random-14, 02-random-15, 02-random-16, 02-random-17, 02-random-18, 02-random-19, 02-random-20, 02-random-21, 02-random-22, 02-random-23, 02-random-24, 02-random-25, 02-random-26, 02-random-27, 02-random-28, 02-random-29, 02-random-30, 02-random-31, 02-random-32, 02-random-33, 02-random-34, 02-random-35, 02-random-36, 02-random-37, 02-random-38, 02-random-39
Case Name Status Exec Time Memory
00-sample-00 AC 1 ms 256 KB
00-sample-01 AC 1 ms 384 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-03 AC 1 ms 384 KB
01-handmade-04 AC 27 ms 32384 KB
01-handmade-05 AC 1 ms 512 KB
01-handmade-06 AC 3 ms 2688 KB
01-handmade-07 AC 23 ms 32384 KB
02-random-08 AC 6 ms 5888 KB
02-random-09 AC 1 ms 384 KB
02-random-10 AC 5 ms 4224 KB
02-random-11 AC 3 ms 2560 KB
02-random-12 AC 4 ms 2816 KB
02-random-13 AC 4 ms 3840 KB
02-random-14 AC 3 ms 1664 KB
02-random-15 AC 6 ms 5760 KB
02-random-16 AC 7 ms 7168 KB
02-random-17 AC 5 ms 3712 KB
02-random-18 AC 8 ms 7936 KB
02-random-19 AC 5 ms 5888 KB
02-random-20 AC 2 ms 1664 KB
02-random-21 AC 13 ms 13696 KB
02-random-22 AC 21 ms 23296 KB
02-random-23 AC 3 ms 2432 KB
02-random-24 AC 15 ms 16384 KB
02-random-25 AC 15 ms 15488 KB
02-random-26 AC 7 ms 7808 KB
02-random-27 AC 3 ms 1920 KB
02-random-28 AC 4 ms 3584 KB
02-random-29 AC 12 ms 13824 KB
02-random-30 AC 3 ms 2688 KB
02-random-31 AC 15 ms 16128 KB
02-random-32 AC 5 ms 5760 KB
02-random-33 AC 4 ms 3456 KB
02-random-34 AC 4 ms 3328 KB
02-random-35 AC 16 ms 17536 KB
02-random-36 AC 6 ms 4992 KB
02-random-37 AC 1 ms 512 KB
02-random-38 AC 3 ms 1792 KB
02-random-39 AC 13 ms 15616 KB