제출 #707020

#제출 시각아이디문제언어결과실행 시간메모리
707020VladPislaru은행 (IZhO14_bank)C++17
71 / 100
1073 ms19804 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;

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);
        }
    }

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

    for (int i = 1; i < n; i++) {
        unordered_set <int> aux;
        for (int j : poss[i])
            for (int k : sol)
                if (nr_bit[j] + nr_bit[k] == nr_bit[j | k])
                    aux.insert(j | k);
        sol = aux;
    }
    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...