Advertisement
Josif_tepe

Untitled

Apr 20th, 2023
759
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.31 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <map>
  5. #include <cstring>
  6. #include <queue>
  7. #include <algorithm>
  8. //#include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11. const int maxn = 1005 * 1005;
  12. vector<int> masks[maxn];
  13. int salary[maxn];
  14. int notes[maxn];
  15. int dp[20][1 << 20];
  16. int rec(int at, int bitmask) {
  17.     if(at == -1) {
  18.         return 1;
  19.     }
  20.  
  21.     if(dp[at][bitmask] != -1) {
  22.         return dp[at][bitmask];
  23.     }
  24.     int result = 0;
  25.     for(int i = 0; i < masks[salary[at]].size(); i++) {
  26.         int tmp_mask = masks[salary[at]][i];
  27.         if((tmp_mask & bitmask) == tmp_mask) {
  28.             result |= rec(at - 1, bitmask ^ tmp_mask);
  29.         }
  30.     }
  31.     return dp[at][bitmask] = result;
  32. }
  33. int main() {
  34.     ios::sync_with_stdio(0);
  35.     int n, m;
  36.     cin >> n >> m;
  37.  
  38.     for(int i = 0; i < n; i++) {
  39.         cin >> salary[i];
  40.     }
  41.     for(int i = 0; i < m; i++) {
  42.         cin >> notes[i];
  43.     }
  44.     for(int bitmask = 0; bitmask < (1 << m); bitmask++) {
  45.         int sum = 0;
  46.         for(int i = 0; i < m; i++) {
  47.             if(bitmask & (1 << i)) {
  48.                 sum += notes[i];
  49.             }
  50.         }
  51.         masks[sum].push_back(bitmask);
  52.     }
  53.     memset(dp, -1, sizeof dp);
  54.     cout << (rec(n - 1, (1 << m) - 1) == 1 ? "YES" : "NO") << endl;
  55.     return 0;
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement