Advertisement
EmadMoh178

Untitled

Aug 14th, 2022
765
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.94 KB | None | 0 0
  1. see#include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define ll long long
  9. #define nl "\n"
  10. #define mod 1'000'000'007
  11. #define cin(v) for (auto &i : v) cin >> i;
  12. #define cin2d(grid, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) cin >> grid[i][j];
  13. #define cout(v) for (auto &i : v) cout << i << " ";cout << '\n';
  14. #define cout2d(grid, n, m) for(int i = 0; i < n; i++, cout << nl) for(int j = 0; j < m && cout << grid[i][j]; j++)
  15. #define all(v) v.begin(), v.end()
  16. #define rall(v) v.rbegin(),v.rend()
  17. #define fixed(n) fixed << setprecision(n)
  18. #define ceil(n, m) (((n) / (m)) + ((n) % (m) ? 1 : 0))
  19. #define ordered_set tree <int, null_type, greater_equal<int>, rb_tree_tag, tree_order_statistics_node_update>  
  20.  
  21. void SicParvisMagna()
  22. {
  23.     ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  24. #ifndef ONLINE_JUDGE
  25.     freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
  26. #endif
  27. }  
  28.  
  29. struct box{
  30.     int time, num, mask;
  31. };
  32.  
  33. int n, m;
  34. vector<box>v;    
  35. vector<vector<int>>dp;  
  36.  
  37. int FindMin(int idx, int mask){
  38.     if(mask == (1 << n) - 1)
  39.         return 0;
  40.     if(idx == m) return 1e9;
  41.     int& ret = dp[idx][mask];
  42.     if(~ret) return ret;
  43.     ret = min(FindMin(idx + 1, mask), v[idx].time + FindMin(idx + 1, mask | v[idx].mask));
  44.     return ret;
  45. }
  46.  
  47. void solve()
  48. {
  49.     cin >> n >> m, v.resize(m), dp.assign(m, vector<int>((1 << n), -1));
  50.     vector<int>temp;
  51.     for(int i = 0; i < m && cin >> v[i].time >> v[i].num; i++){
  52.         int mask = 0;
  53.         for(int j = 0, x; j < v[i].num && cin >> x; j++)
  54.             mask |= (1 << (x - 1));
  55.         v[i].mask = mask;
  56.     }
  57.     int ans = FindMin(0, 0);
  58.     cout << (ans >= 1e9 ? -1 : ans) << nl;
  59. }  
  60.  
  61. int main()  
  62. {
  63.     SicParvisMagna();
  64.     int t = 1;
  65.     // cin >> t;  
  66.     while(t--)
  67.         solve();
  68.     return 0;
  69. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement