Submission #1189728

#TimeUsernameProblemLanguageResultExecution timeMemory
1189728rcllBank (IZhO14_bank)C++20
100 / 100
99 ms8832 KiB
#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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...