CCCPaste

Untitled

#include 
#include 
#include 
using namespace std;
int subjects, people;
struct professor {
    int salary;
    int n;
    vector subject;
};
professor candidate[205];
int candidates;
int dp[201][1 << 8][1 << 8];
int rec(int at, int bitmask1, int bitmask2) {
    if((__builtin_popcount(bitmask1) == subjects) and (__builtin_popcount(bitmask2) == subjects)) {
        return 0;
    }
    if(at == candidates) {
//        cout << bitmask1 << " " << bitmask2 << endl;
        return 1e8;
    }
    if(dp[at][bitmask1][bitmask2] != -1) {
        return dp[at][bitmask1][bitmask2];
    }
    int new_mask1 = bitmask1;
    int new_mask2 = bitmask2;
    for(int i = 0; i < candidate[at].n; i++) {
        int p = candidate[at].subject[i];
        if(new_mask1 & (1 << p)) {
            new_mask2 |= (1 << p);
        }
        else {
            new_mask1 |= (1 << p);
        }
    }
    int result = 1e8;
    result = min(result, rec(at + 1, new_mask1, new_mask2) + candidate[at].salary);
    result = min(result, rec(at + 1, bitmask1, bitmask2));
    
    return dp[at][bitmask1][bitmask2] = result;
}

int main() {
    memset(dp, -1, sizeof dp);
    cin >> subjects >> people;
    professor initial[people + 1];
    int initial_salary = 0;
    int mask1 = 0, mask2 = 0;
    for(int i = 0; i < people; i++) {
        cin >> initial[i].salary >> initial[i].n;
        initial_salary += initial[i].salary;
        for(int j = 0; j < initial[i].n; j++) {
            int p;
            cin >> p;
            p--;
            initial[i].subject.push_back(p);
            
            if(mask1 & (1 << p)) {
                mask2 |= (1 << p);
            }
            else {
                mask1 |= (1 << p);
            }
        }
    }
    cin >> candidates;
    
    
    for(int i = 0; i < candidates; i++) {
        cin >> candidate[i].salary >> candidate[i].n;
        for(int j = 0; j < candidate[i].n; j++) {
            int p;
            cin >> p;
            candidate[i].subject.push_back(p - 1);
        }
    }
    cout << rec(0, mask1, mask2) + initial_salary << endl;
    return 0;
}
// 011