Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <cstring>
- using namespace std;
- int subjects, people;
- struct professor {
- int salary;
- int n;
- vector<int> 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement