Submission #751549

#	Time	Username	Problem	Language	Result	Execution time	Memory
751549		hanlulu	Bank (IZhO14_bank)	C++14	19 / 100	98 ms	8504 KiB

bank

//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);
	/*
	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.
	*/
	string ans = "NO";
	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 == m ) {
			ans = "YES";
			break;
		}		
		//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;
			}
			else if (salary[dp[s].first] > dp[s].second + notes[i])
			{
				dp[(1<<i) | s].first = dp[s].first;
 				dp[(1<<i) | 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 << ans << endl;		
    return 0;
}

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