Submission #887642

#	Time	Username	Problem	Language	Result	Execution time	Memory
887642		asdasdqwer	Bank (IZhO14_bank)	C++14	71 / 100	793 ms	262144 KiB

bank

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,sse4")
    
#include <bits/stdc++.h>
using namespace std;

signed main() {
    int n, m;cin>>n>>m;
    vector<int> a(n);
    for (int &x:a)cin>>x;
    
    vector<int> b(m);
    for (int &x:b)cin>>x;
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    for (int i=0;i<n;i++) {
        for (int j=0;j<m;j++) {
            if (a[i] == b[j]) {
                a.erase(a.begin()+i);
                b.erase(b.begin()+j);
                n--;m--;
                i--;
                break;
            }
        }
    }

    if (n == 0) {
        cout<<"YES\n";
        return 0;
    }

    else if (m == 0) {
        cout<<"NO\n";
        return 0;
    }

    vector<vector<int>> bitmasks;
    
    for (int i=0;i<n;i++) {
        vector<int> btm;
        int x = a[i];
        int mx = (1 << m);
        for (int j=1;j<mx;j++) {
            int sm = 0, cp = j;
            int cnt=0;
            while (cp) {
                if ((cp & 1) == 1) {
                    sm += b[m-cnt-1];
                    if (sm > x) break;
                }
                cnt++;
                cp >>= 1;
            }
    
            if (sm == x) {
                btm.push_back(j);
            }
        }
    
        if (btm.size() == 0) {
            cout << "NO\n";
            return 0;
        }
    
        bitmasks.push_back(btm);
    }
    
    vector<int> ger;
    for (int x:bitmasks[0]) {
        ger.push_back(x);
    }
    
    for (int i=1;i<n;i++) {
        vector<int> copy;
        for (int x:bitmasks[i]) {
            for (int y:ger) {
                if ((x & y) == 0) {
                    copy.push_back((x | y));
                }
            }
        }
    
        ger = copy;
    }
    
    if (ger.size()) {
        cout << "YES\n";
    }
    
    else {
        cout << "NO\n";
    }
}

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