제출 #707101

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
707101		VladPislaru	은행 (IZhO14_bank)	C++17	100 / 100	509 ms	19728 KiB

bank

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

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