Submission #884464

#	Time	Username	Problem	Language	Result	Execution time	Memory
884464		iag99	Bank (IZhO14_bank)	C++17	100 / 100	112 ms	16984 KiB

bank

#include "bits/stdc++.h"
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;

//string m;


signed main()
{
    fast;
	 int n,m;
	 cin>>n>>m;
	 vector<int> a(n);
	 vector<int> b(m);
	 for(int i=0; i<n; i++)
	 {
		 cin>>a[i];
	 }
	 for(int i=0; i<m; i++)
	 {
		 cin>>b[i];
	 }
	 vector<int> leftover(1 << m, -1); //leftover amount after using banknotes in mask
	vector<int> people_covered(1 << m, -1); //max prefix of peopel we can cover with banknotes in mask
	leftover[0] = 0;
	people_covered[0] = 0;
	for(int mask=0; mask<(1<<m); mask++)
	{
		for(int i=0; i<m; i++)
		{
			if(!(mask & (1<<i))) continue;
			int pmask=mask & ~(1<<i);
			if (people_covered[pmask] == -1) { continue; }

			if(leftover[pmask]+b[i] < a[people_covered[pmask]])
			{
				people_covered[mask]=people_covered[pmask];
				leftover[mask]=leftover[pmask]+b[i];
			}
			else if(leftover[pmask]+b[i]==a[people_covered[pmask]])
			{
				people_covered[mask]=people_covered[pmask]+1;
				leftover[mask]=0;
			}
		}
		if(people_covered[mask]==n)
		{
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
}

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