제출 #1189728

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1189728		rcll	은행 (IZhO14_bank)	C++20	100 / 100	99 ms	8832 KiB

bank

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n,m;
	cin >> n >> m;
	vector<int> people(n);
	vector<int> banknotes(m);
	for (int &p:people) { 
        cin>>p; 
    }
	for (int &b:banknotes) { 
        cin>>b; 
    }
	vector<int> leftover(1 << m,-1);
	vector<int> people_covered(1 << m,-1);
	leftover[0]=0;
	people_covered[0]=0;
	for (int s=0; s < (1 << m); s++) {
		for (int last=0; last < m; last++) {
			if ((s & (1 << last)) == 0) { 
                continue; 
            }
			int prev=s & ~(1 << last);
			if (people_covered[prev] == -1) { 
                continue; 
            }
			int new_amt=leftover[prev] + banknotes[last];
			int curr_target=people[people_covered[prev]];
			if (new_amt < curr_target) {
				people_covered[s]=people_covered[prev];
				leftover[s]=new_amt;
			}
			else if (new_amt == curr_target) {
				people_covered[s]=people_covered[prev] + 1;
				leftover[s]=0;
			}
		}
		if (people_covered[s] == n) {
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
}

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