Submission #751557

#TimeUsernameProblemLanguageResultExecution timeMemory
751557hanluluBank (IZhO14_bank)C++14
100 / 100
77 ms8532 KiB
//https://oj.uz/problem/view/IZhO14_bank
#include <bits/stdc++.h>
using namespace std; 
const int MOD = 1e9+7;
 
int main()
{
	//freopen("bank.in","r",stdin);
	//freopen("bank.out","w",stdout);
  	int n, m;
  	cin >> m >> n;
  	vector< int > notes(n),salary(m);
 	for (int i = 0; i < m ;i++)
  	{
  		cin >> salary[i];
  	} 	
	for (int i = 0; i < n ;i++)
  	{
  		cin >> notes[i];
  	}

	vector< pair<int,int> > dp(1<<n,{-1,0});
	/*
	dp[00001011b] ={x,y} means select first,second and 4th notes can satisfy first x people
	and also has y money left.  
	we add new note as the last one to cover the current people.
	*/
 
	dp[0] = {0,0} ;//empty, dealing with salary[0],no money left. 
	for (int s = 0; s < (1<<n); s++)
	{
		//cout << s << " " << dp[s].first << " " << dp[s].second << endl;
		if(dp[s].first == -1) continue;	//should not use invalid status.
		//cout <<salary[dp[s].first]  << endl;
		for (int i = 0 ;i < n; i++) {
			if ( (1<<i) & s ) //already has ith notes, skip
				continue;
	
			//try to finish people dp[s].first	using current notes[i]
 			if (salary[dp[s].first] == dp[s].second + notes[i])//just enough to pay
 			{
 				dp[(1<<i) | s].first = dp[s].first+1;
 				dp[(1<<i) | s].second = 0;
			 	if (dp[(1<<i) | s].first == m ) {
						cout <<  "YES" << endl;
						return 0;
					}						
			}
			else if (salary[dp[s].first] > dp[s].second + notes[i])
			{
				dp[(1<<i) | s].first = dp[s].first;
 				dp[(1<<i) | s].second  =  dp[s].second + notes[i];	
							
			}
			//cout <<((1<<i) | s) <<" "<< dp[(1<<i) | s].first << " dp " << dp[(1<<i) | s].second << endl;
			//if bigger do nothing, as we can not use it.
		}

	}	
 
	cout << "NO" << endl;		
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...