Advertisement
KiK0S

Untitled

Jan 18th, 2018
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.36 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4.  
  5. int dp[21][1<<20];
  6.  
  7. vector<int> masks[20001];
  8. int costs[21];
  9. int money[21];
  10. int n, m;
  11. void calc(int pos, int mask){
  12.     if(dp[pos][mask] != -1) return;
  13.     if(pos == n){
  14.         dp[pos][mask] = 1;
  15.         return;
  16.     }
  17.     for(int i = 0; i < masks[costs[pos]].size(); i++){
  18.         if((mask & masks[costs[pos]][i]) == masks[costs[pos]][i]){
  19.             calc(pos+1, mask ^ masks[costs[pos]][i]);
  20.             if(dp[pos+1][mask ^ masks[costs[pos]][i]]){
  21.                 dp[pos][mask] = 1;
  22.                 return;
  23.             }
  24.         }
  25.     }
  26.     dp[pos][mask] = 0;
  27. }
  28.  
  29. signed main(){
  30.     ios_base::sync_with_stdio(0);
  31.     cin.tie(0);
  32.     cout.tie(0);
  33.     cin >> n >> m;
  34.     memset(dp, -1, sizeof(dp));
  35.     memset(costs, 0, sizeof(costs));
  36.     memset(money, 0, sizeof(money));
  37.     for(int i = 0; i < 20001; i++){
  38.         masks[i].clear();
  39.     }
  40.     for(int i = 0; i < n; i++){
  41.         cin >> costs[i];
  42.     }
  43.     for(int i = 0; i < m; i++){
  44.         cin >> money[i];
  45.     }
  46.     for(int mask = 0; mask < 1<<m; mask++){
  47.         int sum = 0;
  48.         for(int i = 0; i < m; i++){
  49.             if(mask & (1<<i)) sum += money[i];
  50.         }
  51.         masks[sum].push_back(mask);
  52.     }
  53.  
  54.  
  55.  
  56.     calc(0, (1<<m)-1);
  57.     if(dp[0][(1<<m)-1]) cout<<"YES";
  58.     else cout<<"NO";
  59.     return 0;
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement