제출 #1002809

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1002809		pdao	은행 (IZhO14_bank)	C++14	100 / 100	94 ms	17036 KiB

bank

#include <bits/stdc++.h>
#define int long long
#define vi vector<int>

using namespace std;

signed main() {
	int ppl, banknote;
	cin >> ppl >> banknote;

	vi ppls(ppl), banknotes(banknote), left(1 << banknote, -1), paid(1 << banknote, -1);
	
	for (int i = 0; i < ppl; i++) cin >> ppls[i];
	for (int i = 0; i < banknote; i++) cin >> banknotes[i];
	
	left[0] = 0;
	paid[0] = 0;

	for (int mask = 0; mask < (1 << banknote); mask++) {
		for (int last = 0; last < banknote; last++) {
			if ((mask & (1 << last)) == 0) continue;

			int prev = mask & ~(1 << last);

			if (paid[prev] != -1) {
				int cur = left[prev] + banknotes[last]; // current ppl
				
				int curm = ppls[paid[prev]]; // target money for current ppl

				if (cur < curm) {
					paid[mask] = paid[prev];
					left[mask] = cur;
				}

				else if (cur == curm) {
					paid[mask] = paid[prev] + 1;
					left[mask] = 0;
				}
			}
		}
		
		if (paid[mask] == ppl) {
			cout << "YES" << endl;
			return 0;
		}
	}
	cout << "NO" << endl;
}

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