ceva_megamind

Комплексные обеды

Jan 25th, 2020
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. int main() {
  9.     int n,a,cc,m;
  10.     cin >> n;
  11.     set<int> wish;
  12.     map <int,int> price;
  13.     for (int i = 0; i < n; i++) {
  14.         cin >> a >> cc;
  15.         wish.insert(a);
  16.         price[a] = cc;
  17.     }
  18.     cin >> m;
  19.     int k[20], c[20];
  20.     vector<set<int>>lunch(20);
  21.     int kek;
  22.     for (int i = 0; i < m; i++) {
  23.         cin >> k[i] >> c[i];
  24.         for (int j = 0; j < k[i]; j++) {
  25.             cin >> kek;
  26.             if (wish.find(kek)!=wish.end())
  27.                 lunch[i].insert(kek);
  28.         }
  29.     }
  30.     int final=1<<m;
  31.     long long minans=1e15, ans;
  32.     for (int mask = 0; mask < final; mask++) {
  33.         set<int>dishes;
  34.         ans = 0;
  35.         for (int pos = 0; pos < m; pos++) {
  36.             if (mask & (1 << pos)) {
  37.                 ans += c[pos];
  38.                 for (int food : lunch[pos])
  39.                     dishes.insert(food);
  40.             }
  41.         }
  42.         for (int elem : wish)
  43.             if (dishes.find(elem)==dishes.end())
  44.                 ans+=price[elem];
  45.         if (ans < minans)
  46.             minans = ans;
  47.     }
  48.     cout << minans;
  49. }
Add Comment
Please, Sign In to add comment