Submission #867830

#TimeUsernameProblemLanguageResultExecution timeMemory
867830pete555Bank (IZhO14_bank)C++17
100 / 100
100 ms8848 KiB
#include<bits/stdc++.h>
using namespace std;

int main()
{
	int N, M;
	cin >> N >> M;
	int sala[N], bank[M];
	for(int& i: sala) cin >> i;
	for(int& i: bank) cin >> i;
	vector<int> covered(1<<M, -1); //maximum people covered from this subset
	vector<int> leftover(1<<M, -1); //leftover money from this subset
	covered[0] = 0; leftover[0] = 0;
	for(int mask=1; mask<(1<<M); mask++){
		for(int i=0; i<M; i++){
			if(!(mask&(1<<i))) continue;
			int prev = mask^(1<<i);
			if(leftover[prev] == -1) continue;
			int target = covered[prev];
			if(leftover[prev] + bank[i] < sala[target]){
				leftover[mask] = leftover[prev] + bank[i];
				covered[mask] = covered[prev];
			}
			else if(leftover[prev] + bank[i] == sala[target]){
				leftover[mask] = 0;
				covered[mask] = covered[prev] + 1;
			}
		}
		if(covered[mask] == 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...