Submission #65472990

---

Source Code Expand

#include <bits/stdc++.h>
#define REP(i, n)     for(int i = 0; i < (int)(n); ++i)
#define RREP(i, n)    for(int i = (int)(n); i-- > 0;)
#define FOR(i, l, r)  for(int i = (int)(l); i < (int)(r); ++i)
#define RFOR(i, r, l) for(int i = (int)(r); i-- > (int)(l);)
#define ALL(v)        std::begin(v), std::end(v)
using llong = long long;
using vi    = std::vector<int>;
using vvi   = std::vector<vi>;
using pii   = std::pair<int, int>;
using namespace std;
constexpr int       INF  = 1e9;
constexpr long long LINF = 1e18;
constexpr double    EPS  = 1e-10;
constexpr int       MOD  = 998'244'353;
constexpr int       MOD2 = 1e9 + 7;

template <typename Type>
inline std::istream &operator>>(std::istream &is, std::vector<Type> &v) {
    for(auto &elem : v) is >> elem;
    return is;
}

template <typename Type>
inline std::ostream &operator<<(std::ostream &os, const std::vector<Type> &v) {
    for(auto iter = v.cbegin(); iter != v.cend(); ++iter) os << (iter == v.cbegin() ? "" : " ") << *iter;
    return os;
}

#ifdef DEBUG

#include "debug.hpp"

#else

#define debug(...) static_cast<void>(0)

#endif

template <typename Type>
std::vector<Type> table(std::size_t n, const Type &val) { return std::vector<Type>(n, val); }

template <typename... Args>
auto table(std::size_t n, const Args &...args) { return std::vector(n, table(args...)); }

constexpr int popcount32(uint32_t bit) {
    bit -= (bit >> 1) & 0x55555555U;
    bit = (bit & 0x33333333U) + ((bit >> 2) & 0x33333333U);
    bit = (bit + (bit >> 4)) & 0x0f0f0f0fU;
    bit += bit >> 8;
    bit += bit >> 16;
    return bit & 0x3fU;
}

constexpr int popcount64(uint64_t bit) {
    bit -= (bit >> 1) & 0x5555555555555555ULL;
    bit = (bit & 0x3333333333333333ULL) + ((bit >> 2) & 0x3333333333333333ULL);
    bit = (bit + (bit >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
    bit += bit >> 8;
    bit += bit >> 16;
    bit += bit >> 32;
    return bit & 0x7fULL;
}

int main(){
    int n;
    int m;
    cin>>n>>m;

    vector<llong> c(n);
    cin>>c;

    vector<int> a(m,0);
    REP(i,m){
        int k;
        cin>>k;

        REP(j,k){
            int b;
            cin>>b;
            b--;
            a[i]|=1<<b;
        }
    }
    debug(a);

    llong ans=LINF;
    auto calc=[&](int bit)->llong{
        llong res=0;
        REP(i,n){
            if(bit>>i&1) res+=c[i];
            if(bit>>(n+i)&1) res+=c[i];
        }
        return res;
    };
    REP(bit,1<<(2*n)){
        bool ng=false;
        REP(i,m){
            int bit2=(bit&a[i])|(bit&a[i]<<n);
            if(popcount32(bit2)<2){
                ng=true;
                break;
            }
        }
        if(ng) continue; 
        debug(bitset<20>(bit));
   
        auto tmp=calc(bit);
        ans=min(ans,tmp);
    }
    
    cout<<ans<<endl;
}

Submission Info

Judge Result