Submission #884428

#	Time	Username	Problem	Language	Result	Execution time	Memory
884428		iag99	Bank (IZhO14_bank)	C++17	0 / 100	20 ms	2512 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;
	/*
	 * dp[i][mask]=we can give the first i people their salaries using the banknotes in mask
	 * For each mask, calculate pairs of (values you can get, bitmask corresponding to it), then update dp[i+1] if value is equal to a[i+1]
	 */
	 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<vector<bool>> dp(n+1, vector<bool>(1<<m,false));
	 dp[0][0]=true;
	 for(int i=0; i<n; i++)
	 {
		 for(int mask=0; mask< (1<<m); i++)
		 {
			 set<pair<int,int>> vals;
			 vals.insert({0,0});
			 for(int j=0; j<m; j++)
			 {
				 if(!(mask & (1<<j)))
				 {
					 for(pair<int,int> p : vals)
					 {
						 int cmask=p.second;
						 if(!(cmask & (1<<j))) vals.insert({p.first+b[j], cmask | (1<<j)});
						 if(p.first+b[j]==a[i])
						 {
							 dp[i+1][cmask | (1<<j)]=true;
						 }
					 }
				 }
			 }
		 }
	 }
	 if(dp[n][1<<m])
	 {
		 cout<<"YES"<<endl;
	 }
	 else
	 {
		 cout<<"NO"<<endl;
	 }
}

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