Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define int long long
- using namespace std;
- int dp[21][1<<20];
- vector<int> masks[20001];
- int costs[21];
- int money[21];
- int n, m;
- void calc(int pos, int mask){
- if(dp[pos][mask] != -1) return;
- if(pos == n){
- dp[pos][mask] = 1;
- return;
- }
- for(int i = 0; i < masks[costs[pos]].size(); i++){
- if((mask & masks[costs[pos]][i]) == masks[costs[pos]][i]){
- calc(pos+1, mask ^ masks[costs[pos]][i]);
- if(dp[pos+1][mask ^ masks[costs[pos]][i]]){
- dp[pos][mask] = 1;
- return;
- }
- }
- }
- dp[pos][mask] = 0;
- }
- signed main(){
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin >> n >> m;
- memset(dp, -1, sizeof(dp));
- memset(costs, 0, sizeof(costs));
- memset(money, 0, sizeof(money));
- for(int i = 0; i < 20001; i++){
- masks[i].clear();
- }
- for(int i = 0; i < n; i++){
- cin >> costs[i];
- }
- for(int i = 0; i < m; i++){
- cin >> money[i];
- }
- for(int mask = 0; mask < 1<<m; mask++){
- int sum = 0;
- for(int i = 0; i < m; i++){
- if(mask & (1<<i)) sum += money[i];
- }
- masks[sum].push_back(mask);
- }
- calc(0, (1<<m)-1);
- if(dp[0][(1<<m)-1]) cout<<"YES";
- else cout<<"NO";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement