제출 #648397

#제출 시각아이디문제언어결과실행 시간메모리
648397MEGalodon은행 (IZhO14_bank)C++14
100 / 100
70 ms8572 KiB
#include <iostream>

#include <vector>


using std::cout;

using std::endl;

using std::vector;


int main() {

	int people_num;

	int note_num;

	std::cin >> people_num >> note_num;

	vector<int> people(people_num);

	vector<int> banknotes(note_num);

	for (int& p : people) {

		std::cin >> p;

	}

	for (int& b : banknotes) {

		std::cin >> b;

	}


	vector<int> leftover(1 << note_num, -1);

	vector<int> people_covered(1 << note_num, -1);

	leftover[0] = 0;

	people_covered[0] = 0;

	for (int s = 0; s < (1 << note_num); s++) {

		for (int last = 0; last < note_num; 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];

			// the salary of the current person we're going to try to pay

			int curr_target = people[people_covered[prev]];

			// if it's still not enough, just increment the leftover pile

			if (new_amt < curr_target) {

				people_covered[s] = people_covered[prev];

				leftover[s] = new_amt;
              	break;

			}

			/*

			 * or it's exactly right, in which case reset the leftover count

			 * and increment the covered amount

			 */

			else if (new_amt == curr_target) {

				people_covered[s] = people_covered[prev] + 1;

				leftover[s] = 0;
               break;

			}

		}

		// we've covered all the people!

		if (people_covered[s] == people_num) {

			cout << "YES" << endl;

			return 0;

		}

	}

	cout << "NO" << endl;

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...