This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 21;
vector<int> possibleMasks[N];
int memo[N][(1 << N)], n, m;
int solve(int i, int msk) {
if(i == n)
return 1;
int &ret = memo[i][msk];
if(~ret)
return ret;
ret = 0;
for(int new_msk : possibleMasks[i]) {
if((msk & new_msk) == new_msk) {
if (solve(i + 1, msk ^ new_msk))
return ret = 1;
}
}
return ret;
}
void solve() {
cin >> n >> m;
vector<int> a(n), b(m);
for(int &x : a)
cin >> x;
for(int &y : b)
cin >> y;
memset(memo , -1 , sizeof(memo));
for(int msk = 1 ; msk < (1 << m) ; ++msk) {
int sum = 0;
for(int i = 0 ; i < m ; ++i) {
if((msk >> i) & 1) {
sum += b[i];
}
}
for(int i = 0 ; i < n ; ++i) {
if(a[i] == sum) {
possibleMasks[i].push_back(msk);
}
}
}
cout << (solve(0, (1 << m) - 1) ? "YES" : "NO" ) << "\n";
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
#else
#endif
int tc = 1, cs = 1;
// cin >> tc;
while(tc--){
solve();
}
return 0;
}
Compilation message (stderr)
bank.cpp: In function 'int main()':
bank.cpp:52:17: warning: unused variable 'cs' [-Wunused-variable]
52 | int tc = 1, cs = 1;
| ^~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |