제출 #707101

#제출 시각아이디문제언어결과실행 시간메모리
707101VladPislaru은행 (IZhO14_bank)C++17
100 / 100
509 ms19728 KiB
#include <bits/stdc++.h>

using namespace std;


int n, m;
int a[1005], b[1005];
int sum[(1 << 20) + 5], nr_bit[(1 << 20) + 5];

unordered_set <int> poss[1005], sol;

pair <int, int> c[1005];


int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < m; i++)
        cin >> b[i];
    for (int j = 0; j < (1 << m); j++) {
        for (int k = 0; k < m; k++)
            if (j & (1 << k)) {
                sum[j] += b[k];
                nr_bit[j]++;
            }

    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << m); j++) {
            if (sum[j] == a[i])
                poss[i].insert(j);
        }
        c[i] = {poss[i].size(), i};
    }
    sort(c, c + n);

    for (int j : poss[c[0].second])
        sol.insert(j);

    for (int i = 1; i < n; i++) {
        unordered_set <int> aux;
        for (int j : poss[c[i].second])
            for (int k : sol)
                if (nr_bit[j] + nr_bit[k] == nr_bit[j | k])
                    aux.insert(j | k);
        sol = aux;
        if (sol.size() == 0) {
            cout << "NO\n";
            return 0;
        }
    }
    if (sol.size())
        cout << "YES\n";
    else cout << "NO\n";

    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...