Submission #1303776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303776		vladneagu	Bank (IZhO14_bank)	C++20	71 / 100	1093 ms	13260 KiB

bank

#include <iostream>
#include <map>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
const int maxn=21;
int n,m;
int vals[maxn];
map<int,vector<int>> fv;
bool fvv[1005];
int coins[maxn];
signed main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        cin>>vals[i];
        fvv[vals[i]]=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;
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29