Submission #1268537

#TimeUsernameProblemLanguageResultExecution timeMemory
1268537brinleyhongBank (IZhO14_bank)C++20
52 / 100
1 ms708 KiB
// [BANK]
//05-09-2025
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define sp " "
const int maxn = 20;
int n, m, a[maxn+5], b[maxn+5];
vector <int> v[maxn+5];
void precomp()
{
    cin >> n >> m;
    for (int i = 0; i<n; ++i) cin >> a[i];
    for (int i = 0; i<m; ++i) cin >> b[i];
}
bool backtrack(int i, int val)
{
    if (i==n) return true;
    bool res = false;
    int sz = v[i].size();
    for (int j = 0; j<sz; ++j)
    {
        int h = v[i][j];
        int temp = val|h;
        if (temp == val+h)
        {
            res = res | backtrack(i+1, temp);
        }
    }
    return res;
}
void subs()
{
    for (int S = 0; S<(1<<m); ++S)
    {
        int temp = 0;
        for (int j = 0; j<m; ++j)
        {
            if (S&(1<<j)) temp += b[j];
        }
        for (int i = 0; i<n; ++i)
            if (temp == a[i]) v[i].push_back(S);
    }
    if (backtrack(0, 0)) cout << "YES";
    else cout << "NO";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    precomp();
    if (n<=20 && m<=14)
        subs();
    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...