Submission #7749374


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 t; cin>>t;
            t--;
            T[i]|=1<<t;
        }
        // cout<<(bitset<10>)T[i]<<endl;
    }

    vector<int> dp(1<<N,INF);
    dp[0]=0;
    for(int i=0;i<M;i++){
        for(int S=0;S<(1<<N);S++){
            chmin(dp[S|T[i]],dp[S]+a[i]);
        }
    }
    int ans=dp[(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 857 Byte
Status AC
Exec Time 6 ms
Memory 256 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 256 KB
00-sample-02 AC 1 ms 256 KB
01-handmade-03 AC 1 ms 256 KB
01-handmade-04 AC 6 ms 256 KB
01-handmade-05 AC 1 ms 256 KB
01-handmade-06 AC 2 ms 256 KB
01-handmade-07 AC 6 ms 256 KB
02-random-08 AC 2 ms 256 KB
02-random-09 AC 1 ms 256 KB
02-random-10 AC 2 ms 256 KB
02-random-11 AC 2 ms 256 KB
02-random-12 AC 2 ms 256 KB
02-random-13 AC 2 ms 256 KB
02-random-14 AC 2 ms 256 KB
02-random-15 AC 2 ms 256 KB
02-random-16 AC 2 ms 256 KB
02-random-17 AC 2 ms 256 KB
02-random-18 AC 3 ms 256 KB
02-random-19 AC 2 ms 256 KB
02-random-20 AC 1 ms 256 KB
02-random-21 AC 3 ms 256 KB
02-random-22 AC 5 ms 256 KB
02-random-23 AC 2 ms 256 KB
02-random-24 AC 4 ms 256 KB
02-random-25 AC 4 ms 256 KB
02-random-26 AC 2 ms 256 KB
02-random-27 AC 2 ms 256 KB
02-random-28 AC 2 ms 256 KB
02-random-29 AC 3 ms 256 KB
02-random-30 AC 2 ms 256 KB
02-random-31 AC 4 ms 256 KB
02-random-32 AC 2 ms 256 KB
02-random-33 AC 2 ms 256 KB
02-random-34 AC 2 ms 256 KB
02-random-35 AC 4 ms 256 KB
02-random-36 AC 2 ms 256 KB
02-random-37 AC 1 ms 256 KB
02-random-38 AC 2 ms 256 KB
02-random-39 AC 3 ms 256 KB