Submission #887579

#	Time	Username	Problem	Language	Result	Execution time	Memory
887579		mertozel	Bank (IZhO14_bank)	C++11	46 / 100	72 ms	8640 KiB

bank

#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);


			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;

			}

			/*

			 * 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;

			}

		}

		// we've covered all the people!

		if (people_covered[s] == people_num) {

			cout << "YES" << endl;

			return 0;

		}

	}

	cout << "NO" << endl;

}

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