Submission #1303780

#TimeUsernameProblemLanguageResultExecution timeMemory
1303780vladneaguBank (IZhO14_bank)C++20
100 / 100
563 ms9984 KiB
#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <set>
#include <vector>
#pragma GCC optimize("O3","unroll-loops")
using namespace std;
const int maxn=21;
int n,m;
int vals[maxn];
unordered_map<int,vector<int>> fv;
bool fvv[1005];
int coins[maxn];
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>vals[i];
        fvv[vals[i]]=1;
    }
    sort(vals+1,vals+n+1);
    for (int i=0;i<m;i++) {
        cin>>coins[i];
    }
    for (int mask=0;mask<(1<<m);mask++) {
        int sum=0;
        for (int i=0;i<m;i++) {
            if (mask&(1<<i)) {
                sum+=coins[i];
            }
        }
        if (fvv[sum]==1) {
            fv[sum].push_back(mask);
        }
    }
    set<int> s(fv[vals[1]].begin(),fv[vals[1]].end());
    for (int i=2;i<=n;i++) {
        set<int> s2;
        if (s.size()==0)break;
        for (auto it:fv[vals[i]]) {
            for (auto it2:s) {
                if ((it&it2)==0)s2.insert(it|it2);
            }
        }
        s.swap(s2);
    }
    if (s.size()) {
        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...