Submission #751551

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
751551	2023-05-31T18:17:26 Z	hanlulu	Bank (IZhO14_bank)	C++14	19 / 100	81 ms	8500 KB

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.
	*/
 
	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;
	
		//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 && dp[(1<<i) | s].second == 0) {
						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 += 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;
}

Subtask #1

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	81 ms	8500 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	5 ms	8404 KB	Output is correct
9	Correct	66 ms	8500 KB	Output is correct

Subtask #2

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Incorrect	1 ms	212 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	2 ms	340 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	81 ms	8500 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	5 ms	8404 KB	Output is correct
9	Correct	66 ms	8500 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Incorrect	1 ms	212 KB	Output isn't correct
12	Halted	0 ms	0 KB	-