Advertisement
Guest User

Untitled

a guest
Jan 25th, 2020
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <set>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. int n,m;
  10. int mi = 1000000000;
  11.  
  12. vector <int> a, c;
  13.  
  14. vector < pair <int, vector <int> > > v;
  15.  
  16. bool cmp(pair<int, vector <int> > a, pair<int, vector <int> > b){
  17. return a.first < b.first;
  18. }
  19.  
  20. void f(int counter, string is_taken){
  21. if (counter < m){
  22. f(counter + 1, is_taken + '0');
  23. f(counter + 1, is_taken + '1');
  24. }
  25. else{
  26. set <int> s;
  27. int cur_sum = 0;
  28. for(int i = 0; i < counter; ++i){
  29. if (is_taken[i] == '1'){
  30. cur_sum += v[i].first;
  31. for(int j = 0; j < v[i].second.size(); ++j){
  32. s.insert(v[i].second[j]);
  33. }
  34. }
  35. }
  36.  
  37. for(int i = 0; i < n; ++i){
  38. if (s.find(a[i]) == s.end()){
  39. cur_sum += c[i];
  40. }
  41. }
  42.  
  43. mi = min(cur_sum, mi);
  44. //for(auto it : s) cout << it << " ";
  45. //cout << endl;
  46. }
  47. }
  48.  
  49. int main() {
  50. cin >> n;
  51.  
  52. for(int i = 0, aa, cc; i < n; ++i){
  53. cin >> aa >> cc;
  54. a.push_back(aa);
  55. c.push_back(cc);
  56. }
  57.  
  58. cin >> m;
  59. for(int i = 0, kk, cc; i < m; ++i){
  60. cin >> kk >> cc;
  61. vector <int> input(kk);
  62. for(int j = 0; j < kk; ++j){
  63. cin >> input[j];
  64. }
  65. v.push_back({cc, input});
  66. }
  67.  
  68. f(0, "");
  69.  
  70. cout << mi << endl;
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement