Submission #728572

#TimeUsernameProblemLanguageResultExecution timeMemory
728572Azther0zBank (IZhO14_bank)C++11
100 / 100
129 ms8532 KiB
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin >> n >> m;
	int people[n],note[m];
	for(int i=0;i<n;i++)
		cin >> people[i];
	for(int i=0;i<m;i++)
		cin >> note[i];
	vector<int> moneyleft(1<<m,-1),paidpeople(1<<m,-1);
	moneyleft[0]=paidpeople[0]=0;
	for(int subset=1;subset<(1<<m);subset++)
	{
		for(int j=0;j<m;j++)
		{
			int prev=subset^(1<<j);
			if(subset&(1<<j)&&paidpeople[prev]!=-1)
			{
				int current=moneyleft[prev]+note[j];
				int target=people[paidpeople[prev]];
				if(current<target)
				{
					moneyleft[subset]=current;
					paidpeople[subset]=paidpeople[prev];
				}
				else if(current==target)
				{
					moneyleft[subset]=0;
					paidpeople[subset]=paidpeople[prev]+1;
				}
			}
		}
		if(paidpeople[subset]==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...