제출 #1325955

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

bank

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

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> paid(1 << m, -1), left_over(1 << m, -1);
	paid[0] = left_over[0] = 0;
	for (int mask = 0; mask < (1 << m); ++mask) {
        if (paid[mask] == -1) continue;
        for (int i = 0; i < m; ++i) {
            if ((mask >> i) & 1) continue;

            int nxt = paid[mask];
            int new_amount = left_over[mask] + b[i];
            if (new_amount < a[nxt]) {
                paid[mask | (1 << i)] = paid[mask];
                left_over[mask | (1 << i)] = new_amount;
            } else if (new_amount == a[nxt]) {
                paid[mask | (1 << i)] = paid[mask] + 1;
                left_over[mask | (1 << i)] = 0;
            }
        }

        if (paid[mask] == n) {
            cout << "YES" << '\n';
            return 0;
        }
	}

	cout << "NO" << '\n';
	return 0;
}

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