Submission #1336621

#TimeUsernameProblemLanguageResultExecution timeMemory
1336621pn197Bank (IZhO14_bank)C++17
27 / 100
1093 ms712 KiB
#include <bits/stdc++.h>
using namespace std;

const int N=22, MASK=(1<<20)+2;
int n, m, a[N], b[N];
bool dp[N][MASK];
vector<int> msk[N];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i=1;i<=n;++i)
        cin >> a[i];
    for(int i=1;i<=m;++i)
        cin >> b[i];
    for(int i=1;i<=n;++i){
        for(int mask=0;mask<(1<<m);++mask){
            int sum=0;
            for(int j=1;j<=m;++j)
                if(mask&(1<<(j-1)))
                    sum+=b[j];
            if(sum==a[i])
                msk[i].push_back(mask);
        }
    }
    dp[0][0]=1;
    for(int i=1;i<=n;++i){
        for(int mask=0;mask<(1<<m);++mask){
            for(int submask:msk[i]){
                if(submask>mask) continue;
                dp[i][mask]|=dp[i-1][mask^submask];
            }
        }
    }
    bool ans=0;
    for(int mask=0;mask<(1<<m);++mask)
        ans|=dp[n][mask];
    if(ans)
        cout << "YES";
    else cout << "NO";
    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...