제출 #1325944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1325944		marcus06	은행 (IZhO14_bank)	C++20	0 / 100	1 ms	332 KiB

bank

#include <bits/stdc++.h>
using namespace std;
using lli = long long;

int f[21][1 << 20];

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	int n, m;
	cin >> n >> m;
	vector <int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];

	vector <int> b(m);
	for (int i = 0; i < m; ++i) cin >> b[i];

	vector <int> total(1 << m);
	for (int mask = 0; mask < (1 << m); ++mask) {
        for (int i = 0; i < m; ++i) {
            if ((mask >> i) & 1) total[mask] += b[i];
        }
	}

	vector <vector <int>> good_mask(n);
	for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < (1 << m); ++mask) {
            if (total[mask] == a[i]) good_mask[i].emplace_back(mask);
        }
	}

    int full_mask = (1 << m) - 1;
    f[0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int mask = 0; mask < (1 << m); ++mask) {
            if (f[i][mask] == 0) continue;
            for (auto x: good_mask[i]) {
                if (x & mask == 0) f[i + 1][mask | x] |= f[i][mask];
            }
        }
    }

    int possible = 0;
    for (int mask = 0; mask < (1 << m); ++mask) possible |= f[n][mask];
    cout << (possible ? "YES" : "NO") << '\n';
	return 0;
}

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