Advertisement
Josif_tepe

Untitled

May 26th, 2022
994
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cstring>
  4. using namespace std;
  5. int subjects, people;
  6. struct professor {
  7.     int salary;
  8.     int n;
  9.     vector<int> subject;
  10. };
  11. professor candidate[205];
  12. int candidates;
  13. int dp[201][1 << 8][1 << 8];
  14. int rec(int at, int bitmask1, int bitmask2) {
  15.     if((__builtin_popcount(bitmask1) == subjects) and (__builtin_popcount(bitmask2) == subjects)) {
  16.         return 0;
  17.     }
  18.     if(at == candidates) {
  19. //        cout << bitmask1 << " " << bitmask2 << endl;
  20.         return 1e8;
  21.     }
  22.     if(dp[at][bitmask1][bitmask2] != -1) {
  23.         return dp[at][bitmask1][bitmask2];
  24.     }
  25.     int new_mask1 = bitmask1;
  26.     int new_mask2 = bitmask2;
  27.     for(int i = 0; i < candidate[at].n; i++) {
  28.         int p = candidate[at].subject[i];
  29.         if(new_mask1 & (1 << p)) {
  30.             new_mask2 |= (1 << p);
  31.         }
  32.         else {
  33.             new_mask1 |= (1 << p);
  34.         }
  35.     }
  36.     int result = 1e8;
  37.     result = min(result, rec(at + 1, new_mask1, new_mask2) + candidate[at].salary);
  38.     result = min(result, rec(at + 1, bitmask1, bitmask2));
  39.    
  40.     return dp[at][bitmask1][bitmask2] = result;
  41. }
  42.  
  43. int main() {
  44.     memset(dp, -1, sizeof dp);
  45.     cin >> subjects >> people;
  46.     professor initial[people + 1];
  47.     int initial_salary = 0;
  48.     int mask1 = 0, mask2 = 0;
  49.     for(int i = 0; i < people; i++) {
  50.         cin >> initial[i].salary >> initial[i].n;
  51.         initial_salary += initial[i].salary;
  52.         for(int j = 0; j < initial[i].n; j++) {
  53.             int p;
  54.             cin >> p;
  55.             p--;
  56.             initial[i].subject.push_back(p);
  57.            
  58.             if(mask1 & (1 << p)) {
  59.                 mask2 |= (1 << p);
  60.             }
  61.             else {
  62.                 mask1 |= (1 << p);
  63.             }
  64.         }
  65.     }
  66.     cin >> candidates;
  67.    
  68.    
  69.     for(int i = 0; i < candidates; i++) {
  70.         cin >> candidate[i].salary >> candidate[i].n;
  71.         for(int j = 0; j < candidate[i].n; j++) {
  72.             int p;
  73.             cin >> p;
  74.             candidate[i].subject.push_back(p - 1);
  75.         }
  76.     }
  77.     cout << rec(0, mask1, mask2) + initial_salary << endl;
  78.     return 0;
  79. }
  80. // 011
  81.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement