Submission #1261274

#TimeUsernameProblemLanguageResultExecution timeMemory
1261274medaaBank (IZhO14_bank)C++20
25 / 100
1095 ms584 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define endl '\n' void SOLVE() { int n, m; cin >> n >> m; vector<int> a(n), b(m); int S = 0; for(auto & val : a) cin >> val, S += val; for(auto & val : b) cin >> val; vector<vector<int>> can(n); for(int i = 1; i < (1 << m); i++){ int sum = 0; for(int j = 0; j < m; j++){ if((i >> j) & 1) sum += b[j]; } for(int j = 0; j < n; j++){ if(a[j] == sum){ can[j].push_back(i); } } } vector<bool> dp(1 << m), ndp; dp[0] = true; for(auto & v : can){ for(int mask : v){ ndp = dp; for(int i = 0; i < (1 << m); i++){ if(dp[i] && (i & mask) == 0){ ndp[i | mask] = true; } } dp.swap(ndp); } } for(int i = 1; i < (1 << m); i++){ if(!dp[i]) continue; int sum = 0; for(int j = 0; j < m; j++){ if((i >> j) & 1) sum += b[j]; } if(sum == S) return void(cout << "YES" << endl); } cout << "NO" << endl; } signed main(){ ios_base::sync_with_stdio(false); cout.tie(nullptr); cin.tie(nullptr); //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int o_o = 1; //cin >> o_o; while(o_o --) SOLVE(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...